[백준] 17142. 연구소 3 (파이썬)

문제

연구소 3

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

 

시간 제한 0.25초 (Python 3 : 1.5초)

메모리 제한 512MB

 

• 공간의 크기 N x N
• 연구소는 빈 칸(0) , 벽(1), 바이러스(2)로 이루어져 있음.
• 바이러스는 활성, 비활성 두 가지 상태로 존재
• 연구소의 바이러스 M개를 활성 상태로 변경하려고 함
• 활성 상태의 바이러스 이동 방법 : 1초에 상하좌우로 인접한 모든 빈 칸으로 동시에 복제.
• 활성 상태의 바이러스 이동 조건 : 
  • 빈 칸(0)을 만난 경우 : 복제
  • 벽(1)을 만난 경우 : 이동 불가
  • 비활성 상태의 바이러스(2)를 만난 경우 : 해당 바이러스가 활성 상태로 변한다.

---

풀이

어떤 바이러스를 활성 상태로 만들까?

처음에는 바이러스의 확산을 시뮬레이션하는 단순 BFS문제인 줄 알았으나,

• M(활성 바이러스 수) <=  총 바이러스 수 <= 10 

해당 조건을 확인해보니, 총 바이러스 수가 활성 바이러스보다 많은 경우에는

어떤 바이러스를 활성화시킬지 선택해야만 했다.

 

위와 같은 상황에서는 총 바이러스 수에서, M개 바이러스만을 선택하여 활성화시켜야 하므로

조합(combinations)를 이용하면 좋을 것이라 판단했다.

 

모든 바이러스는 최대 10마리까지 존재하므로,  조합 10Cr 의 최댓값은 10C5 = 252이며

모든 조합 결과에 대해 BFS를 수행하므로 

 

252 * O(V + E) = 252* O(n^2) * O(4*n^2) = 252 * 12500 = 대략 300만번의 연산으로 해결 가능하다고 판단했다.

 

핵심 알고리즘

1.  완전 탐색을 통해 빈칸의 개수를 구하고, 모든 바이러스의 위치 정보 저장 

2.  어떤 바이러스를 활성 상태로 만들까? -> 조합(combinations)
3.  모든 조합 결과에 대해 활성 상태의 바이러스가 퍼지는 시간 계산하기 -> BFS 반복 수행

4.  결과 출력

 

옵션 1.  모든 빈 칸에 바이러스를 퍼뜨리면 종료
옵션 2.  바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1 출력 및 종료

 

 

이 문제에서의 핵심 구현 포인트를 살펴보자.

1. 어떤 바이러스를 활성 상태로 만들까?

# virus_pos : 모든 바이러스의 x, y 좌표를 저장한 리스트
# m : 활성 상태로 만들 바이러스 수
# blank_cnt : 빈 칸의 개수
# INF : 100000 (임의의 큰 수)
# res : 결괏값

# 2. 어떤 바이러스를 활성 상태로 만들까? -> 조합(combinations) 사용
from itertools import combinations as c

virus_combi = c(virus_pos, m)

res = INF
for virus_list in virus_combi: # 모든 조합 결과에 대하여
	q = deque()
	for virus in virus_list:
		q.append(virus) # 바이러스 위치를 큐에 저장

	tmp = bfs(q, blank_cnt) #BFS 수행
	res = min(res, tmp)

파이썬에는 itertools 모듈이 있어서 permutations(순열), combinations(조합)을 손쉽게 구할 수 있지만

만약에 해당 모듈이 없다면,

백트래킹을 통해 가능한 모든 경우의 수를 찾아나가면 된다.

 

2. 소요 시간을 고려한 BFS

#BFS의 일부분
time += 1
for i in range(length): #큐 길이만큼 반복해주는 for문이 이 문제 해결의 핵심**
    x, y = q.popleft()
    if visited[x][y] == -1:
        visited[x][y] = 1

	#아래로는 일반적인 BFS
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]

        if 0<=nx<n and 0<=ny<n:
            if visited[nx][ny] == -1: #아직 방문하지 않은 칸에 대해
                if board[nx][ny] == 0: # case 1: 빈 칸을 만난 경우
                    q.append((nx, ny))
                    visited[nx][ny] = 1
                    blanks -= 1
                elif board[nx][ny] == 2: # case 2: 비활성된 바이러스를 만난 경우
                    q.append((nx, ny))
                    visited[nx][ny] = 1

2차원 배열에서의 일반적인 BFS는 방문 가능한 칸에 대해

큐에 삽입하고, 다시 하나하나씩 꺼내어 해당 위치를 기점으로 탐색해 나가는 방식이었다.

 

그러나 이 문제에서 위와 같은 로직을 사용할 경우,

탐색을 진행하는 과정에서 현재 몇 초가 지났는지를 알기 어렵다.

 

따라서 조합을 통해 구한 활성 상태의 바이러스들의 좌표를 모두 큐에 담고,

 

1초 동안 큐에 새로 추가된 바이러스 수만큼 탐색하고,

 

완료 시에는 time += 1 증가시키는 방법으로 로직을 재구성하였다.

 

코드

from collections import deque
from itertools import combinations as c
import sys

input = sys.stdin.readline
INF = 100000 #임의의 큰 수

'''
풀이 방법 : BFS + 조합(combinations)
시간 복잡도 : O(n^2)
공간 복잡도 : O(n^2)

1.  완전탐색을 통해 빈 칸의 개수를 구하고, 모든 바이러스의 위치 정보 저장 
2.  어떤 바이러스를 활성 상태로 만들까? -> 조합(combinations)
3.  모든 조합 결과에 대해 활성 상태의 바이러스가 퍼지는 시간 계산하기 -> BFS 반복 수행
4.  결과 출력

옵션 1.  모든 빈 칸에 바이러스를 퍼뜨리면 종료
옵션 2.  바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1 출력 및 종료
'''

def bfs(q, blanks):
	visited = [[-1] * n for _ in range(n)]

	time = 0
	while True:
		length = len(q) # 큐의 길이(=1초 동안 새롭게 추가된 바이러스의 수)
		
		if blanks == 0 or length == 0:
			if blanks == 0: # 옵션 1. 모든 빈 칸에 바이러스를 퍼뜨리면 종료
				return time
			else: # 옵션 2. 바이러스를 어떻게 놓아도 전체에 퍼뜨릴 수 없는 경우
				return INF

		time += 1
		for i in range(length): #큐 길이만큼 반복해주는 for문이 이 문제 해결의 핵심**
			x, y = q.popleft()
			if visited[x][y] == -1:
				visited[x][y] = 1

			for d in range(4):
				nx = x + dx[d]
				ny = y + dy[d]

				if 0<=nx<n and 0<=ny<n:
					if visited[nx][ny] == -1: #아직 방문하지 않은 칸에 대해
						if board[nx][ny] == 0: # case 1: 빈 칸을 만난 경우
							q.append((nx, ny))
							visited[nx][ny] = 1
							blanks -= 1
						elif board[nx][ny] == 2: # case 2: 비활성된 바이러스를 만난 경우
							q.append((nx, ny))
							visited[nx][ny] = 1

n, m = map(int, input().rstrip('\n').split())
board = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]

virus_pos = [] # 바이러스 위치 정보 저장
blank_cnt = 0 # 빈 칸의 개수

# 1. 완전탐색을 통해 빈 칸의 개수를 구하고, 모든 바이러스의 위치 정보 저장 : O(N^2)
for i in range(n):
	for j in range(n):
		if board[i][j] == 0:
			blank_cnt += 1
		
		elif board[i][j] == 2:
			virus_pos.append((i, j))

# BFS를 위한 방향벡터 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# 2. 어떤 바이러스를 활성 상태로 만들까? -> 조합(combinations) 사용
virus_combi = c(virus_pos, m)
res = INF

for virus_list in virus_combi: #모든 조합 결과에 대하여
	q = deque()
	for virus in virus_list:
		q.append(virus)

	tmp = bfs(q, blank_cnt) #BFS 수행
	res = min(res, tmp)

if res == INF: # 옵션 2. 바이러스를 어떻게 놓아도 전체에 퍼뜨릴 수 없는 경우
	print(-1)
else:
	print(res)