[Python] 백준 17142 : 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

풀이방법

• 바이러스의 위치 중 활성화할 m개의 조합에 대해서 bfs를 반복한다. -> iteratools를 사용할 수 있다면 더 편하지만 만약에 불가능하다면 backtracking으로 구현한다. 
• visited에 각각 방문까지 걸리는 시간을 저장해둔다.
• visited에 저장된 시간 중 가장 늦은 시간이 전부에 퍼지는 시간. 
• 단, 이미 바이러스가 있는 곳 (2인 곳)은 시간 체크에서 제외한다.

from collections import deque
from copy import deepcopy
from itertools import combinations

def bfs(starts):
    queue = deque()
    for i, j in starts:
        queue.append((i, j, 0))
    temp = deepcopy(board)
    visited = [[0]*n for _ in range(n)]
    move = [(0,1),(0,-1),(1,0),(-1,0)]
    result = 0
    while queue:
        i, j, time = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = time
        temp[i][j] = 2
        for x, y in move:
            cx = i+x
            cy = j+y
            if 0<=cx<n and 0<=cy<n and board[cx][cy] != 1:
                queue.append((cx,cy,time+1))
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                if visited[i][j] == 0: return float('inf')
                result = max(result, visited[i][j])
    return result
n, m = map(int, input().split())
board = []
for i in range(n):
    board.append(list(map(int, input().split())))
virus = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            virus.append((i, j))

# backtracking으로 구현 
answer = float('inf')
def backtracking(loc, cnt, arr):
    global answer
    if cnt == m:
        answer = min(answer, bfs(arr))
        return
    if loc >= len(virus):
        return
    for i in range(loc, len(virus)):
        arr.append(virus[i])
        backtracking(i+1, cnt+1, arr)
        arr.pop()
backtracking(0,0,[])

# iteratools 사용 
for start in list(combinations(virus, m)):
    answer = min(answer, bfs(start))
    
if answer == float('inf'):
    print(-1)
else:
    print(answer)