파이썬으로 풀어보는 백준 17142번: 연구소 3 (삼성 A형 기출 문제)

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

17142번: 연구소 3

 

내 풀이:

def BFS(lst):
    global ans
    q = []
    for idx in lst:
        q.append(virus[idx])
    visited = [[False] * N for _ in range(N)]
    new = [arr[i][:] for i in range(N)]
    for y, x in q:
        visited[y][x] = True
    result = 0
    while q:
        TF = True
        for c in range(len(q)):
            y, x = q.pop(0)
 
            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
 
                if 0 <= ny <= N-1 and 0 <= nx <= N-1 and not visited[ny][nx]:
                    if new[ny][nx] == 0:
                        new[ny][nx] = 2
                        visited[ny][nx] = True
                        q.append((ny, nx))
                        TF = False
 
                    elif new[ny][nx] == 2:
                        visited[ny][nx] = True
                        q.append((ny, nx))
 
        if TF:
            break
        result += 1
 
 
    for i in range(N):
        for j in range(N):
            if new[i][j] == 0:
                return
 
    if ans > result:
        ans = result
 
 
def order(idx, lst):
    global cnt
    if len(lst) == M:
        BFS(lst)
        return
 
 
    for i in range(lst[-1]+1, len(virus)):
        if i not in lst:
            lst.append(i)
            order(idx + 1, lst)
            lst.pop()
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
ans = 3000
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
virus = []
cnt = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            virus.append((i, j))
            cnt += 1
 
for i in range(len(virus)):
    order(1, [i])
 
if ans == 3000:
    print(-1)
else:
    print(ans)

Python3, 1000ms

전형적인 BFS 탐색 문제인 것 같다. 다만 주의해야 할 점은 이미 0은 모두 제거했는데 뒤늦게 활성화된 바이러스가 큐에 들어갈 수 있기 때문에 0이 하나도 발견되지 않은 경우에 while문을 나갈 수 있도록 장치를 해주었다.