[BOJ] 17142 : 연구소 3 [브루트포스/BFS](Python)

문제 링크

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

17142번: 연구소 3

소스 코드

from itertools import combinations
from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n)]
viruses = []
answers = []
walls = 0

for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 0: # 빈칸
            graph[i].append(0)
        elif temp[j] == 1:
            graph[i].append(1) # 벽
            walls += 1
        else:
            graph[i].append(2) # 바이러스
            viruses.append((i,j))

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

def bfs(virus):
    temp_graph = [[-1 for _ in range(n)] for _ in range(n)]
    for x,y in virus:
        temp_graph[x][y] = 0 # 출발 지점
    max_cnt = 0 # 최대 숫자
    
    queue = deque(virus)
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n: # 그래프 범위 충족
                # 원래 빈칸이면서 아직 방문한 적이 없을 때
                if graph[nx][ny] == 0 and temp_graph[nx][ny] == -1:
                    temp_graph[nx][ny] = temp_graph[x][y] + 1
                    queue.append((nx,ny))
                    max_cnt = max(max_cnt,temp_graph[nx][ny])
                # 비활성 바이러스이면서 아직 방문한 적이 없을 때 -> 업데이트 x
                elif graph[nx][ny] == 2 and temp_graph[nx][ny] == -1:
                    temp_graph[nx][ny] = temp_graph[x][y] + 1
                    queue.append((nx,ny))
    
    wall = 0 # 현재 그래프 내의 이동 불가능 지역
    for i in range(n):
        wall += temp_graph[i].count(-1) # 이동이 불가능한 칸

    if wall == walls: # 도달하지 못한 영역이 없는 경우
        answers.append(max_cnt) 

cases = combinations(viruses,m) # m개의 활성 바이러스
for case in cases:
    bfs(case)

if not answers:
    print(-1)
else:
    print(min(answers))

 

해설

• 브루트포스, 완전탐색, BFS

문제를 이해하는 것 자체가 굉장히 까다로웠던 것 같습니다..

딱 봤을 땐 그냥 케이스별로 BFS를 돌리고 최솟값을 뽑아내면 되는 것이라고 생각했는데 막상 풀어보니 반례를 처리하는게 쉽지 않았습니다.

핵심 포인트를 위주로 간단히 내용을 정리해보겠습니다.

 

1. 완전 탐색

이 문제가 완전 탐색이라는 것은 아주 쉽게 파악할 수 있습니다.

입력으로 받는 그래프의 정보에서 2의 개수를 k라고 할 때 활성화된 바이러스의 개수는 m이기 때문에 총 kCm개의 조합이 가능하죠!

물론 사람이 봤을 때는(n,m이 작은 숫자인 경우) 어디서 출발하는 것이 가장 이상적인지 쉽게 파악할 수 있지만,

컴퓨터는 그게 불가능하기 때문에 가능한 모든 경우의 수에 대해서 모두 계산을 해보고 최소의 값을 따로 추출해야 합니다.

 

이를 위해서 itertools의 combinations를 불러오고 각 경우를 case라는 변수에 담아 BFS를 실행해야 합니다.

cases = combinations(viruses,m) # m개의 활성 바이러스
for case in cases:
    bfs(case)

여기서 viruses는 그래프 입력을 받을 때 바이러스(2)의 위치를 튜플 형태로 저장한 리스트입니다.

 

2. BFS

우리는 주어진 활성화 함수들의 위치로부터 그래프를 탐색하면서 최단 이동거리를 구하게 됩니다.

따라서 현재 위치를 기준으로 이동 가능한 좌표가 또 있는지 추가로 탐색하며 이동 횟수를 기록할 수 있는 BFS 방식을 택합니다.

 

다들 아시겠지만 BFS의 아주 기본적인 형태는

1) deque를 사용해서 이 큐가 완전히 빌 때까지 반복문을 돌린다.

queue = deque(virus)
while queue:
    x,y = queue.popleft()

2) 현재 노드에서 이동 가능한 지역이 있는지를 for문과 if문의 조합을 통해 파악한다.

이때 이동 가능 여부는 그래프의 인덱스 범위 내에 속하는지와 이전에 방문한 적이 없는 좌표인지를 확인하여 따질 수 있다.

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n:

3) if문 이하의 모든 조건을 만족하는 경우 queue에 추가하여 해당 노드를 중심으로 추가 탐색(BFS)을 수행한다.

if graph[nx][ny] == 0 and temp_graph[nx][ny] == -1:
    temp_graph[nx][ny] = temp_graph[x][y] + 1
    queue.append((nx,ny))
    max_cnt = max(max_cnt,temp_graph[nx][ny])
# 비활성 바이러스이면서 아직 방문한 적이 없을 때 -> 업데이트 x
elif graph[nx][ny] == 2 and temp_graph[nx][ny] == -1:
    temp_graph[nx][ny] = temp_graph[x][y] + 1
    queue.append((nx,ny))

이 과정을 반복하는 것이 일반적인 BFS의 작동 방식입니다.

 

3. 최소 이동 횟수 기록하기

아마 이것이 가장 까다로웠던 부분인 것 같습니다.

일반적으로는 BFS를 모두 돌리고 나서 그래프에 표시된 것들을 확인하기만 하면 되는데,

이 문제에서는 그렇게 했을 때에 대한 수많은 반례가 존재했습니다.

이는 활성화되지 않은 바이러스들 때문입니다.

 

우선 포인트를 먼저 짚어보면 다음과 같습니다.

1. 활성화되지 않은 바이러스를 거쳐 갈 때에도 똑같이 1초가 걸린다.
2. 활성화되지 않은 바이러스를 제외하면 더이상 이동할 곳이 없는 경우 탐색을 종료한다.

1번은 활성화된 바이러스가 빈 칸(0)을 거쳐 이동하는 것과 완전히 동일합니다.

문제가 되는 것은 2번입니다.

만약 벽(1)과 바이러스(2)로만 가득찬 그래프가 주어지는 경우 바이러스가 퍼지는데 걸리는 최소 시간은 0초입니다.

 

왜냐하면 '비활성화 바이러스'도 '바이러스'이기 때문이죠!!!

다만 이녀석은 활성화되기 전까지는 가만히 있을 뿐이고, 만약 이녀석들을 제외한 모든 빈 칸이 바이러스로 채워지게 된다면 이 녀석은 굳이 활성화 될 필요도 없는 것입니다.

 

예를 들어,

* 0 2 1
1 1 1 1

* 2 2 1
1 1 1 1

이렇게 한 번만 바이러스가 빈 칸을 채우기만 해도 모든 영역이 바이러스로 가득 찬 것이죠.

하지만 비활성화 바이러스를 빈 칸과 동일시하게 되면 문제가 발생합니다.

1)
0 1 2 * 0
1 1 0 0 1

2)
0 1 2 2 0
1 1 0 0 1

3)
0 1 2 2 2
1 1 2 2 1

이런 경우라면 우측의 빈 칸은 모두 채울 수 있습니다.

하지만 좌측의 빈 칸은 벽 때문에 애초에 채울 수가 없는 것이죠.

 

따라서 우리는 BFS를 끝까지 돌려서 빈 칸이 남아있는지 확인해야 합니다.

wall = 0 # 현재 그래프 내의 이동 불가능 지역
for i in range(n):
    wall += temp_graph[i].count(-1) # 이동이 불가능한 칸

if wall == walls: # 도달하지 못한 영역이 없는 경우
    answers.append(max_cnt)

현재 그래프에서 이동하지 못한 지역의 개수가 기존 그래프의 벽의 개수와 동일하지 않다면 벽에 막혀서 채워지지 않은 칸이 존재한다는 뜻이죠.

따라서 둘의 값이 동일할 때만 정답 리스트에 후보를 추가해주도록 합니다.

 

그리고 이동 횟수를 업데이트하는 것은 '비활성화 바이러스(2)'에 옮겨 갈 때가 아닌 '빈 칸(0)'에 옮겨 갈 때만 해당합니다.

왜냐하면 비활성화 바이러스가 활성화 되고 나서 모든 작업이 끝났는지, 혹은 추가로 이동한 다음에 끝났는지 알 수가 없기 때문입니다.

# 원래 빈칸이면서 아직 방문한 적이 없을 때
if graph[nx][ny] == 0 and temp_graph[nx][ny] == -1:
    temp_graph[nx][ny] = temp_graph[x][y] + 1
    queue.append((nx,ny))
    max_cnt = max(max_cnt,temp_graph[nx][ny])
# 비활성 바이러스이면서 아직 방문한 적이 없을 때 -> 업데이트 x
elif graph[nx][ny] == 2 and temp_graph[nx][ny] == -1:
    temp_graph[nx][ny] = temp_graph[x][y] + 1
    queue.append((nx,ny))

위 코드에서 max_cnt = max(max_cnt, temp_graph[nx][ny]) 가 왜 위의 조건문에만 해당하는지 잘 생각해보시길 바랍니다!!