(Python/파이썬) - 백준(BOJ) 17141번 : 연구소 2

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

17141번: 연구소 2

---

• 문제 : 

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

 

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

 

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

 

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

 

 

---

• 풀이 :

BFS와 완전탐색 문제였습니다.

 

그래프 탐색과 완전탐색은 코딩테스트에 섞어서 내기 좋은 단골 문제인 것 같습니다.

(주로 DFS로 나옵니다. BFS는 너무 쉬워서인듯....)

 

 문제 해결 알고리즘의 흐름입니다.

 

1. 주어진 N x N의 보드를 완전탐색으로 순회하며 바이러스의 좌표들을 virus 배열에 담습니다.

 

2. 바이러스의 좌표들에서 M개를 뽑는 조합(이 경우에는 순서가 상관 없기 때문에 조합이 맞습니다.)을 만들고 조합마다 bfs를 실시합니다.

 

3. bfs의 리턴값은 모든 블록들을 감염시키거나, 또는 감염시키지 못했을 때 최소 횟수입니다. 이 값을 갱신하여 최소횟수를 출력하면 됩니다.

 

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
from itertools import combinations


# 상, 하, 좌, 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

input = sys.stdin.readline
answer = float("inf") # 최솟값을 찾기 위해 초깃값을 inf로 설정

def bfs(v):
    queue = deque(v)
    visited = [[-1 for _ in range(N)]  for _ in range(N)]
    m = 0 # 최소 횟수를 찾기 위한 변수
    for x,y in queue:
        visited[x][y] = 0
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0 <= ax < N and 0 <= ay < N:
                if visited[ax][ay] == -1 and board[ax][ay] != 1:
                    queue.append([ax,ay])
                    visited[ax][ay] = visited[x][y] + 1
                    m = max(m,visited[x][y] + 1) # 최소 횟수로 갱신
    
    # bfs가 끝난 이후 바이러스에 감염되지 않은 빈 칸이 있다면 감염시킬수 없는 경우
    # 따라서 inf를 리턴해줌
    for i in range(N):
        for j in range(N):
            if visited[i][j] == -1 and board[i][j] != 1:
                return float("inf")
    return m



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

# 바이러스의 좌표 찾기
for i in range(N):
    for j in range(N):
        if board[i][j] == 2:
            virus.append([i,j])

# 바이러스의 좌표들 중 M개를 뽑은 모든 경우에 대해서 bfs 수행하며 최솟값 갱신
for v in combinations(virus,M):
    answer = min(bfs(v),answer)
    
# 탐색하지 못하는 경우 answer에는 inf값이 들어있다
if answer == float("inf"):
    print(-1)
else:
    print(answer)