[python] 백준 17142 연구소 3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

문제 해결

• 시물레이션 + BFS가 바로 생각나는 문제
• 바이러스가 전염이 되는 것과 안되는 것이 처음에 존재하므로 존재하는 것을 고르는 경우의 수 combination을 사용한다.
• 각각의 경우 BFS를 사용하여 벽인 부분을 빼고 계속 전염시킨다.
• 만약 비전염 바이러스를 만나면 비전염바이러스가 전염이 되는 것과 같다.
• 모두 전염이 될 때의 시간을 결과값으로 받아서 최소값을 구하면 된다.

※ ps) 전형적인 삼성 기출문제 냄새가 난다.

 

from collections import deque
def combinations(arr,n):
    result = []
    if n==0:
        return [[]]
    for i in range(0,len(arr)):
        elem = arr[i]
        rest_arr = arr[i+1:]
        for c in combinations(rest_arr,n-1):
            result.append([elem]+c)
    return result
def bfs(comb):
    dxs = [-1,1,0,0]
    dys = [0,0,-1,1]
    que = deque()
    visited = [[-1]*n for _ in range(n)]
    result = 0
    for x, y in comb:
        que.append((x,y))
        visited[x][y] = 0
    while que:
        x, y = que.popleft()
        for dx, dy in zip(dxs,dys):
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<n:
                if board[nx][ny]==0 and visited[nx][ny] == -1:
                    que.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1
                    result = max(result,visited[nx][ny])
                elif board[nx][ny] ==2 and visited[nx][ny] == -1:
                    que.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1
    for i in range(n):
        for j in range(n):
            if board[i][j] != 1 and visited[i][j] == -1:
                return 10**6
    return result

if __name__=='__main__':
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    cell = []
    wall = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] == 2:
                cell.append((i,j))
            elif board[i][j] == 1:
                wall += 1
    if wall+len(cell) == n**2:
        print(0)
        exit()
    answer = 10**6
    for comb in combinations(cell,m):
        answer = min(answer,bfs(comb))
    print(answer if answer != 10**6 else -1)