Ray`s Tech Lab

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

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

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

https://www.acmicpc.net/problem/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))

이 문제를 통해 얻은 것.

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

그래프같은 걸 탐색할 때, 너비를 우선으로 탐색을 진행하는 것을 너비우선탐색, 영어로는 Breadth First Search라고 하며 줄여서 BFS라고도 부른다. 어떠한 시작점이 있을 때, 그로부터 가까운 것들부터 탐색해나가는 방법으로 맹목적인 탐색을 할 때 사용가능한 방법이다. 이 녀석은 '최단 경로'를 찾아주기 때문에 최단길이를 보장해야 할 때 많이 쓰인다.

예시)

이 방법을 구현하려면, 큐(queue)가 필요하다.

그럼 이걸 파이썬으로 구현해보자.

우선 그래프는 다음과 같이 딕셔너리 형태로 표현해봤다.

graph = {
    1 : [2, 3, 4],
    2 : [1, 3],
    3 : [1, 2, 4, 5],
    4 : [1, 3],
    5 : [3, 6],
    6 : [5]
}           # 키에 연결된 value에 있는 리스트가 그 key에 연결된 애들임

그리고 BFS를 도와줄 큐는 다음과 같이 해보자.

queue = []                       # 큐를 리스트 형태로 구현

queue.append(something)          # 큐에 요소를 넣는 동작 : append  ->큐의 뒤쪽에 추가
queue.pop(0)                     # 큐에 요소를 빼는 동작 : pop(0)  ->큐의 앞쪽에 있는 걸 뺌

 그럼 BFS를 다음과 같이 만들 수 있다.

def BFS(graph, start_node):
    visited = []                           # 방문한 요소들이 이 리스트에 저장됨
    queue = [start_node]                   # 큐

    while queue:                           # 큐에 뭔가 있는 동안 이하 내용을 반복한다
        node = queue.pop(0)                # 큐의 제일 앞에 있는 놈을 빼와서
        if node not in visited:            # 만약 이 놈이 방문한 적이 없다면
            visited.append(node)           # 방문처리
            print(node)                    # 그 녀석 출력
            queue.extend(graph[node])      # 그 녀석과 연결된 요소들(graph[node])를 queue에 추가

근데 이 방법에는 문제점이 있다.

그것을 확인하기 위해 다음과 같이 코드 중간중간에 print를 써서 현재 queue와 visited에 있는 값들을 하나하나 확인해보고,  걸리는 시간까지 알아보자.

import time

def BFS(graph, start_node):
    start = time.time()
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            print(f'방문 처리 후 visited : {visited}')
            queue.extend(graph[node])
            print(f'큐에 연결된 요소 추가 후 queue : {queue}')
        print("-"*10)
    print(time.time()-start)

대략 0.007초가 걸렸다.

이 코드의 문제점은 그럼 뭘까?

어떤 요소를 방문처리해주고(visited.append(node))

그 요소와 연결된 요소들(graph[node])를 큐에 추가해줄 때, 방문한 적 없는 요소들만 추가해야 한다.

근데 위 코드는 일단 연결된 요소들 전부 큐에 추가해주고, 나중에 큐에서 꺼낼 때 꺼낸 값이 방문한 적이 있는지 없는지를 판단하기 때문에 쓸데없이 시간을 낭비하는 꼴이 된다.

그래서 다음과 같이 바꿔줄 수 있다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            for nd in graph[node]:             # 연결된 요소들에 대해 하나하나 따진다
                if nd not in visited:          # 방문한 적 없는 요소여야
                    queue.append(nd)           # 큐에 추가

그러나 이 방법도 문제점이 있다. 큐에 원소들을 추가해주는 작업을 하는 부분을 보면 graph[node]에 해당하는 리스트의 원소들을 루프문으로 돌기 때문에, 시간낭비가 역시 생길 수 있다!

이 문제점을, set이라는 자료형를 사용해 상당히 간편하게 해결할 수 있다.

그래서 다음과 같이 해준다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            queue += (set(graph[node]) - set(visited))

그러나 아직까지도 문제가 있다..ㅋㅋㅋㅋㅋㅋ

큐에서 제일 첫 번째 녀석을 빼주는 queue.pop(0)이 문젠데, 이 녀석의 시간복잡도가 O(n)이라는 것.

이는 collection 라이브러리에 있는 deque를 사용해 해결가능하다.

그리고 visited가 리스트로 되어있는데,

if in 또는 if not in방법은 리스트에서 하면 이 역시 시간복잡도가 O(n)이다.

따라서 visited를 딕셔너리 또는 집합(set)으로 해주는 게 더 빠르다!

그래서, 다음과 같이 해주자.

from collections import deque

def BFS(graph, start_node):
    visited = {}
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited[node] = True
            print(node)            
            queue += (set(graph[node]) - set(visited))