17141: 연구소 2

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

17141번: 연구소 2

설명

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

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

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

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

핵심 아이디어

해당 문제는 삼성 기출문제는 아니지만 기출문제인 연구소 3과 유사한 문제라서 가져왔다. 핵심 개념은 비슷하다.

• 완전 탐색 + BFS

코드 설명

해당 코드는 연구소 3에서 풀어던 방식과는 로직을 조금 다르게 구성해서 풀었고, 다른 사람의 코드를 참조해서 해결했다.

import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations

n,m = map(int, input().split())
graph = [list(map(int, input().split()))]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
virus_pos = []
for x in range(n):
	for y in range(n):
		if graph[x][y] == 2:
			virus_pos.append((x,y))
def bfs(v):
	q = deque(v)
	visited = [[-1] * n for _ in range(n)]
	time = 0

	for x,y in q:
		if visited[x][y] == -1:
			visited[x][y] = 0
	while q:
		x,y = q.popleft()
		for d in range(4):
			nx = x + dx[d]
			ny = y + dy[d]
			if (0<=nx<n) and (0<=ny<n) and visited[nx][ny] == -1:
				visited[nx][ny] = visited[x][y] + 1
				q.append((nx,ny))
				# 예시로 6초
				time = max(time, visited[nx][ny])
	# BFS 탐색 이후 바이러스를 퍼뜨릴 수 없는 경우를 고려
	for x in range(n):
		for y in range(n):
			if visited[x][y] == -1 and graph[x][y] != 1:
				return INF
	return time

INF = int(1e9)
ans = INF
for v in list(combinations(virus_pos,m)):
	ans = min(ans, bfs(v))
if ans == INF:
	print(-1)
else:
	print(ans)