[백준] 17142 - 연구소 3 오답노트

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

17142번: 연구소 3

---

조합과 BFS가 짬뽕된 문제. 바이러스를 놓을 수 있는 위치들에 대한 m개의 조합들을 하나하나 살펴보며 BFS를 돌려 판별하면 된다. 

이 문제에선 고려해야 할 사항이 좀 더 있다. 바로 BFS의 종료조건.

 

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

7576번: 토마토

 

위 문제 "토마토"는 본 문제인 "연구소 3"과 꽤나 유사하다. 익은 토마토가 매 페이즈마다 주변 토마토를 익게 하듯이, 본 문제에서의 바이러스도 매 페이즈마다 주변 칸들에 퍼져 나간다. 또한 모든 토마토가 익을 때까지 최소 며칠이 걸리는지 계산하는 것과 빈 칸이 모두 바이러스가 퍼질 때까지 최소 얼마나 걸리는지를 요구하는 것도 비슷하다.

 

그러나 디테일에 차이가 있다. 토마토 문제는 모든 토마토가 익을 때까지 BFS를 돌려야 한다면, 본 문제는 빈 칸에 바이러스가 채워질 때까지만 BFS를 돌려야 한다. 즉 벽을 제외한 모든 칸이 활성 바이러스로 채워질 때까지 돌리는 게 아니다. 비활성된 바이러스가 있어도 다른 빈 칸들이 남아있지 않다면 더 이상 BFS를 돌릴 필요가 없다.

 

따라서 안 익는 토마토가 있든 없든 일단 Queue가 빌 때까지 BFS를 돌려 가능한 모든 구역의 토마토가 익게 한 다음, Queue가 비고 나면 그제서야 모든 토마토가 익어도 되는지 판단해도 되는 토마토 문제와는 달리, 본 문제는 BFS를 돌릴 때마다 연구소 상황을 체크해야 한다. (무작정 큐가 빌 때까지 돌리면 빈 칸들이 다 찰 때까지가 아니라 벽을 제외한 모든 칸에 활성 바이러스가 퍼질 때까지를 보게 되는 문제로 바뀌니까)

 

즉 빈칸들을 채울 때마다 카운트해주고, 매 BFS마다 현재까지 채운 빈칸의 수와 처음에 셌던 빈칸의 수가 일치하는지를 판단해야 한다. 즉 큐에서 꺼낸 노드마다 상하좌우 네 방향에 대해 방문여부를 확인하고 방문여부를 안 했고 그 칸이 빈칸이면 채운 빈칸의 수를 하나 늘리면 된다.

 

내가 실수한 부분은, 빈칸을 채운 뒤 채운 빈칸의 수를 늘리는 작업과 빈 칸을 다 채웠는지 판단하는 작업을 동시에 안 했다는 거다. 나는 BFS를 할 때 보통 종료조건을 판단하는 작업을 큐에서 노드를 꺼내고 난 바로 다음에 한다. 얘를 들어 지금 꺼낸 노드가 도착지점이라면 지금까지 카운트한 수가 정답이다! 처럼 판단하는 것. 즉 이 문제는 이런 습관에 따라 처음에 다음과 같이 BFS코드를 짰다.

 

while q:
    1. 만약 지금까지 채운 빈칸의 수가 처음에 센 빈칸의 수와 같다면 종료하는 코드
    2. 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가한 다음
    지금까지 채운 빈칸 수를 += 1

 

빈칸을 채우고 채운 빈칸 수를 늘리는 작업(2)과 빈칸을 다 채웠는지 판단하는 작업(1)을 동시에 하고 있지 않는 모습이다. 이 때문에 오답이 날 수 있다. 큐에서 노드를 하나 꺼냈는데 x초에 방문한 노드였고, 이 노드의 인접한 빈칸을 채우고 채운 빈칸 수를 늘렸다. 큐에서 다음 노드를 빼냈고 똑같이 x초에 방문한 노드인데, (1)에 의해 지금껏 채운 빈칸 수가 처음에 센 빈칸의 수와 같아 x초에 모든 빈칸을 채웠다고 오답을 뱉게 된다. 사실 x + 1초에 모든 빈 칸이 채워지는 건데 말이다. 만약 임의의 시간 x초에 방문하는 모든 노드들이 방문하지 않은 인접한 빈 칸을 하나 이상씩 가지고 있는게 보장된다면 이런 일은 안 생기겠지만, x초에 방문하는 모든 노드가 방문하지 않은 인접한 빈칸을 가지고 있다는 보장이 없으니 이런 상황이 생긴다.

 

난 그래서 처음에 틀렸다..ㅋㅋㅋㅋㅋ

 

암튼..! 빈칸을 채우고 채운 빈칸 수를 늘리는 작업과 빈칸을 다 채웠는지 판단하는 작업을 동시에 해야 한다. 다음과 같이 바꿀 수 있을 것이다.

 

while q:
    1. 지금 꺼낸 노드가 빈 칸이면 지금껏 채운 빈 칸의 수 += 1
    2. 만약 지금까지 채운 빈칸의 수가 처음에 센 빈칸의 수와 같다면 종료
    3. 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가

 

또는 다음과 같이도 가능하다. 중요한 건 동시에 두 작업을 순서대로 해야 한다는 거.

 

while q:
    1. 꺼낸 노드에 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가한 다음
    지금까지 채운 빈칸 수를 += 1
    2. 지금까지 채운 빈칸 수가 처음에 센 빈칸 수와 같다면 종료. 단 이 작업은 1이 이루어지고 난 이후에만 진행

 

전체 코드는 다음과 같다.

 

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


def solution(n, m, board):
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    empty_count = 0
    virus = []
    for r in range(n):
        for c in range(n):
            if board[r][c] == 2:
                virus.append((r, c))
            elif board[r][c] == 0:
                empty_count += 1

    answers = []

    for activate_viruses in combinations(virus, m):
        q = deque([])
        visited = set()
        for r, c in activate_viruses:
            q.append((r, c, 0))
            visited.add((r, c))

        empty_to_virus_count = 0

        while q:
            r, c, h = q.popleft()
            if board[r][c] == 0:
                empty_to_virus_count += 1
            if empty_to_virus_count == empty_count:
                answers.append(h)
                break
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if nr < 0 or nc < 0 or nr >= n or nc >= n:
                    continue
                if board[nr][nc] != 1 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    q.append((nr, nc, h + 1))

    if answers:
        return min(answers)
    return -1


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

print(solution(N, M, _board))

 

이 문제를 통해 얻은 것.

"다음 노드들에 대한 작업과 종료여부를 판단하는 작업은 동시에 할 것"