17142: 연구소 3

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

17142번: 연구소 3

설명

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

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

기존에 연구소 맵에 존재하는 비활성 바이러스 중, M개를 골라 활성 바이러스로 만들어 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하기. 

핵심 아이디어

시뮬레이션, 구현 초기 상태의 비활성 바이러스 중 M개를 고르는 모든 경우를 탐색하여 바이러스가 퍼지는 최소 시간 구하기.

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

옵션 1. 모든 빈 칸에 바이러스를 퍼뜨리면 종료

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

---

주의

활성 상태인 바이러스는 상 하 좌 우로 인접한 모든 빈칸으로 동시에 복제되며, 1초가 걸린다. 그리고 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성 바이러스로 변한다. → 활성화 바이러스가 비활성 바이러스를 만난다는 것은 그대로 통과한다는 뜻! (지나갈 수 있다는 의미).

그리고 활성화 된 바이러스가 다 퍼져야하는게 아니라 활성화 여뷰는 상관 없이 바이러스만 퍼져 있으면 된다.(연구소에 빈공간을 모두 바이러스 공간으로 만들면 된다.) 또한, 모든 칸에 바이러스가 퍼지는 최소 시간을 구할 때, 활성 상태 바이러스가 비활성 상태인 바이러스 자리까지 도달하는 데에 걸리는 시간은 고려하지 않는다. 즉, time을 갱신할 때는 활성 상태에서만 고려한다.

 

코드 구현

1. 어떤 바이러스를 활성 상태로 만들것인가

파이썬에는 itertools 모듈이 있어, 순열과 조합을 손쉽게 구할 수 있지만 구현 실력이 높이기 위해 직접 함수로 구현해서 사용하는 방법도 연습해보자.

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

virus_combi = list(combinations(virus_pos, m))

ans = INF
for virus_list in virus_combi: # 모든 조합 결과에 대하여
    q = deque()
    for virus in virus_list:
        q.append(virus) # 바이러스 위치를 큐에 저장
    temp = bfs(q, blank_cnt) # BFS 수행
    ans = min(ans, temp)

2. 소요 시간을 고려한 BFS

2차원 배열에서의 일반적인 BFS는 방문 가능한 칸에 대해 큐에 삽입하고, 다시 하나씩 꺼내 해당 위치를 기점으로 탐색해 나가는 방식이다 하지만, 기존 방식과 똑같이 사용하면 탐색하는 과정에서 현재 몇 초가 지났는지 알기 어렵다. 이를 해결하기 위해, 조합을 통해 구한 활성 상태의 바이러스들의 좌표를 모두 큐에 담고 1초 동안 큐에 새로 추가된 바이러스 수 만큼 탐색하고, 완료 시에는 time += 1증가시키는 방법으로 로직을 재구성해야한다. 

def bfs(q, blanks):
	visited = [[False] * 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 # 1초 당안 큐에 새로 추가된 바이러스 수 만큼 탐색하고, 완료 후 +1
        
        for i in range(length) # 큐 길이만큼 반복해주는 for문이 이 문제 해결의 핵심
            x,y = q.popleft()
            if visited[x][y] == False:
                visited[x][y] = True
            
            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] == False : # 아직 방문하지 않은 칸에 대해
                        if graph[nx][ny] == 0: # 빈 칸이라면
                            q.append((nx,ny))
                            visited[nx][ny] = 1
                            blanks -= 1
                        elif graph[nx][ny] == 2: # 비 활성화된 바이러스를 만난 경우
                            q.append((nx,ny))
                            visited[nx][ny] = True

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

# 맵 크기 입력받기
n, m = map(int, input().split())
# 연구소 정보 입력받기
graph = [list(map(int, input().split())) for _ in range(n)]
# 바이러스 이동을 위한 방향
dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            blank_cnt += 1
        elif graph[i][j] == 2:
            virus_pos.append((i,j))

최종 코드 구현 결과

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


import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
# 맵 크기 입력받기
n, m = map(int, input().split())
# 연구소 정보 입력받기
graph = [list(map(int, input().split())) for _ in range(n)]
# 바이러스 이동을 위한 방향
dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

def bfs(q, blanks):
	visited = [[False] * 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] == False:
				visited[x][y] = True

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

				if (0<=nx<n) and (0<=ny<n) and not visited[nx][ny]:
					if graph[nx][ny] == 0: # case 1: 빈 칸을 만난 경우
						q.append((nx,ny))
						visited[nx][ny] = True
						blanks -= 1
					elif graph[nx][ny] == 2: # case 2: 비활성된 바이러스 만난 경우
                    # 비활성 바이러스 위치도 활성화된 바이러스로 바꾸는 것이 아니지만.
                    # 바이러스가 지나갈 수 있는 경로로 고려된다.
						q.append((nx,ny)) # 큐에 넣음으로써 하나의 경로로 고려된다
						visited[nx][ny] = True




# 1. 완전탐색을 통해 빈 칸의 개수를 구하고, 모든 바이러스의 위치 정보 저장
# O(N^2)
for i in range(n):
	for j in range(n):
		if graph[i][j] == 0: # 빈 칸이라면
			blank_cnt += 1
		elif graph[i][j] == 2:  # 바이러스 라면
			virus_pos.append((i,j))
# 2. 어떤 바이러스를 활성 상태로 만들까? -> 조합 사용
virus_combi = list(combinations(virus_pos, m))
INF = int(1e9) # 임의의 큰 수
ans = INF
# 모든 조합 결과에 대하여
for virus in virus_combi:
	q = deque()
	for i in virus:
		q.append(i)

	temp = bfs(q, blank_cnt)
	ans = min(ans, temp)

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