백준-17142-연구소 3

문제

연구소 3

풀이

문제조건 해석

연구소 내에 모든 빈 공간에 바이러스를 전파하는 최소 시간 구하기.

• 주의! 비활성 바이러스가 위치하는 공간을 빈 공간으로 생각하면 안된다.

처음 바이러스를 놓을 수 있는 위치는 10개 이하이고, 그 중 활성 바이러스로 선택하는 개수는 M개

• 최대 $_{10}C_M$개 경우의 수

알고리즘

바이러스 전파는 BFS 이용

• 활성 바이러스에서 시작
• 빈 공간과 비활성 바이러스를 방문하면 활성 바이러스와 같아진다.

경우의 수는 조합을 이용

빈 공간의 수를 BFS전에 구해준다. 이후 BFS하면서 빈 공간의 수보다 바이러스가 방문한 공간이 많아지면 모든 빈 공간에 바이러스가 전파된 것으로 생각할 수 있다.

• BFS가 끝난 뒤 빈 공간의 수 < 방문한 공간의 수이면 모든 빈 공간에 전파할 수 없는 것이다.

코드

from sys import stdin
from itertools import combinations
from collections import deque
input = stdin.readline

n, m = [int(x) for x in input().rstrip().split()]
maps = []  # 연구실 배열
for _ in range(n):
    maps.append([int(x) for x in input().rstrip().split()])

viruses = []  # 바이러스를 놓을 수 있는 위치
cnt = 0  # 빈 칸의 수
for i in range(n):
    for j in range(n):
        if maps[i][j] == 2:
            viruses.append((i, j))
        elif maps[i][j] == 0:
            cnt += 1
MAX_NUM = 2500  # 최대 시간


def bfs(select):
    blank = 0  # 방문한 빈칸의 수
    visited = [[False]*n for _ in range(n)]
    for s in select:
        visited[s[0]][s[1]] = True
    queue = deque(select)
    time = 0
    while queue:
        if blank >= cnt:  # 모든 빈칸 전염시켰으면
            break
        for _ in range(len(queue)):
            i, j = queue.popleft()
            for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                if not (0 <= i+di < n and 0 <= j+dj < n):
                    continue
                if maps[i+di][j+dj] != 1 and not visited[i+di][j+dj]:
                    if maps[i+di][j+dj] == 0:
                        blank += 1  # 다음 방문이 빈칸이면 방문한 빈칸의 수 증가
                    queue.append((i+di, j+dj))
                    visited[i+di][j+dj] = True
        time += 1
    else:  # 전염 불가능
        return MAX_NUM
    return time


answer = MAX_NUM
for select in combinations(viruses, m):
    answer = min(answer, bfs(select))
if answer == MAX_NUM:
    print(-1)
else:
    print(answer)

배운점

난이도 높은 BFS문제는 문제에 대한 이해와 BFS로직에 대해 정확히 이해하고 응용할 수 있어야 해결 가능하다.