17142번. 연구소 3

http://boj.kr/17142 

17142번: 연구소 3

 

 

문제가 이해가 안되서 애 먹었다.

모든 바이러스는 동서남북 방향으로 확산할 때마다 1초가 걸리는데,

비활성화된 바이러스는 활성화되도록 바꾸고/바이러스가 없는 빈칸(0)은 바이러스로 바꾼다.

문제에서 찾으라는 것은 모든 칸에 바이러스가 존재하게 될 때의 시간이다. (벽은 제외하고..)

바이러스의 활성화/비활성화 여부는 상관없고, 모든 칸에 0이 없어질 때의 시간을 찾는 것이다.

참고로 바이러스는 동서남북으로 확산할 때 무조건 1초가 걸린다. 비활성화 바이러스를 활성화시키는데는 0초, 빈칸을 바이러스로 확산시키는데는 1초가 걸린다고 생각하면 나처럼 고생한다.

 

밑의 두 예제를 보면 이해가 될 것이다.

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1
# Answer: 0

2가 몇개고 1이 몇개고 어쩌구저쩌구하지만 주어지는 입력을 보면 빈 칸(0)이 없다. 그래서 답이 0초다.

 

4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0
# Answer: 2

line 3에 있는 두 개의 2를 선택했을 때의 변화는 다음과 같다.

1초: 위아래로 확산되면서 line 2의 빈 칸(0)은 바이러스로, line 4의 비활성화 바이러스(2)는 활성화 바이러스로 바꾼다.

2초: line 4의 활성화 바이러스가 된 2는 line 5의 빈 칸(0)을 바이러스로 바꾼다.

 

 

문제를 해결하기 위해서 먼저 입력을 board[N][N]에 받은 후에,

virus 리스트에는 바이러스들의 위치를 저장했고 empty_origin에는 빈 칸의 갯수를 저장했다.

virus 리스트에 저장된 것들은 모두 비활성화된 바이러스들이다.

이들 중 DFS로 총 M개를 뽑아 이를 활성화 바이러스로 선택했다.

 

그리고 뽑힌 바이러스들을 큐에 넣고 BFS 탐색을 시작한다.

BFS 탐색을 하는 이유는 모든 바이러스에서 동시에 네 방향으로 확산이 일어나기 때문이다.

depth를 시간이라고 생각하고 큐에 넣고 탐색을 돌리되, 반복문을 반복하는 조건은

큐에 바이러스가 있을 때거나 빈 칸이 아직 남아있을 때이다. 둘 중에 하나만 하면 안되고 둘다 만족해야 하는 이유는 

while empty > 0: 만 하면, 빈 칸은 남아있지만 벽으로 인해서 더이상 바이러스가 이동을 하지 못할 때 무한루프를 돌며, 큐에 뭐가 없는데 자꾸 pop을 시도하게 된다.

while queue: 만 하게 되면, 이미 빈 칸은 0개가 되었는데 비활성화된 바이러스만 남아있을 때, 비활성화된 바이러스를 활성화시키는 시간까지 카운트하게 된다.

 

그리고 어차피 큐에 시간(depth)을 넣어서 돌리는데 반복문이 종료되면 이 depth를 리턴하면 되지 굳이 time을 따로 변수로 빼서 저장해야되냐!라고 생각할수도있는데, 생각해보면 마지막 순간의 depth가 큐에 저장되는데 이를 pop하지 않으므로 따로 저장해줘야 한다.

 

# 연구소 3
import sys
from collections import deque


def bfs(selected):
    queue = deque(selected)
    #lab = deepcopy(board)
    visited = [[0 for _ in range(N)] for _ in range(N)]
    empty = empty_origin  # 남은 빈 칸의 갯수
    time = 0  # 빈 칸의 갯수를 0으로 만드는 데까지 걸린 시간

    for i, j, _ in selected:
        visited[i][j] = 1  # 초기 바이러스의 방문 표시

    while queue and empty > 0:  # 확산 중인 바이러스가 있고 & 빈 칸이 남아있으면
        r, c, depth = queue.popleft()
        for d in range(4):
            next_r, next_c = r + dx[d], c + dy[d]
            if 0 <= next_r < N and 0 <= next_c < N and not visited[next_r][next_c]:
                if board[next_r][next_c] != 1:  # 벽이 아닌데 방문하지 않음 -> 방문해야 함
                    visited[next_r][next_c] = 1
                    queue.append([next_r, next_c, depth + 1])
                    time = depth + 1

                    if board[next_r][next_c] == 0:  # 빈 칸이 바이러스가 될 때마다 empty를 줄임
                        empty -= 1

    if empty > 0:  # 확산이 끝났는데 아직도 0이 남아 있으면 불가능한 것임
        return float('inf')

    return time


def dfs(idx, cnt, selected):
    global min_value
    if cnt == M:
        min_value = min(min_value, bfs(selected))
        return
    for i in range(idx, n_virus):
        dfs(i+1, cnt+1, selected+[virus[i]])  # selected에는 뽑힌 virus의 위치가 추가됨


min_value = float('inf')  # 문제의 답. 최소 시간
input = sys.stdin.readline
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
virus = []  # 바이러스를 놓을 수 있는 위치를 저장
n_virus = 0  # 바이러스를 놓을 수 있는 위치의 갯수
empty_origin = 0  # 빈 칸의 갯수
dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

for i in range(N):
    for j in range(N):
        if board[i][j] == 2:  # 바이러스를 놓을 수 있는 위치를 저장
            virus.append([i, j, 0])  # row, col, depth
            n_virus += 1
        elif board[i][j] == 0:
            empty_origin += 1

dfs(0, 0, [])

if min_value >= float('inf'):
    print(-1)
else:
    print(min_value)