[백준] 연구소 3 - python (17142번)

풀이 전략

하나 씩 탐색하며 최솟값을 찾는 문제는 대부분 BFS 알고리즘을 적용하여 푸는 것이 정답입니당

풀이 과정

1. 빈 칸 세주기

바이러스가 모든 빈 칸에 다 퍼졌는지 나중에 확인하기 위해 처음 빈 칸의 갯수를 미리 세줍니다.

2. 바이러스 위치 정보 저장

바이러스들의 위치를 담고있는 리스트를 만듭니다.

3. combinations로 탐색하기

모든 바이러스에서 전염이 시작되는 것이 아닌 M개의 바이러스에서 최초로 전염이 시작됩니다. 그렇기 때문에 여러개의 바이러스 중에서 M개를 선택하여 BFS탐색을 시작해야 하므로 2번에서 저장한 바이러스 정보들에서 M개를 선택하여 탐색을 시작합니당

4. BFS

infections - 빈 칸에 몇 시간 후에 바이러스가 전파가 됐는지 저장하기 위한 리스트입니다. visited의 역할도 같이 하게 됩니다. DFS가 아닌 BFS로 탐색하기 때문에 초기에 저장된 값이 아닌 값이면 자동으로 방문한 것으로 체크하면 됩니다.
infect_cnt - 빈 칸 중에 처음으로 전파되는 (BFS탐색에 걸리는)칸이면 전염된 빈 칸 수를 늘려주기 위한 변수입니다. 탐색이 끝난 후 1번의 처음 빈칸과 비교해 값이 같으면 모든 칸에 전염이 된 것이고 값이 다르면 전염되지 않은 빈 칸이 있는 것입니다.

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

viruses = []
blanks = 0
for i in range(N):
    for j in range(N):
        if board[i][j] == 2:
            viruses.append((i, j, 0))
        elif board[i][j] == 0:
            blanks += 1

def bound(x, y):
    return 0 <= x < N and 0 <= y < N

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

cur_max = N ** 2

if blanks == 0:
    print(0)
else:
    for combi in combinations(viruses, M):
        q = deque(virus for virus in combi)
        infections = [[N ** 2] * N for _ in range(N)]
        infect_cnt = 0
        mm = 0
        while q:
            x, y, time = q.popleft()
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if bound(nx, ny):
                    if board[nx][ny] == 0:
                        if infections[nx][ny] == N ** 2:
                            infect_cnt += 1
                            infections[nx][ny] = time + 1
                            q.append((nx, ny, time + 1))
                            mm = max(mm, time + 1)
                    elif board[nx][ny] == 2:
                        if infections[nx][ny] == N ** 2:
                            q.append((nx, ny, time + 1))
                            infections[nx][ny] = time + 1
        if infect_cnt == blanks:
            cur_max = min(cur_max, mm)

    if cur_max == N ** 2:
        print(-1)
    else:
        print(cur_max)