JB의 이모저모
[BOJ 17141🥇4] 연구소 2 (Python) 본문
https://www.acmicpc.net/problem/17141
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러
www.acmicpc.net
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 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 2M = 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연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
입력
첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
예제 입력 1
7 3
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
예제 출력 1
5
예제 입력 2
7 3
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2
예제 출력 2
5
예제 입력 3
7 4
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2
예제 출력 3
4
예제 입력 4
7 5
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2
예제 출력 4
3
예제 입력 5
7 3
2 0 2 0 1 1 0
0 0 1 0 1 0 0
0 1 1 1 1 0 0
2 1 0 0 0 0 2
1 0 0 0 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2
예제 출력 5
7
예제 입력 6
7 2
2 0 2 0 1 1 0
0 0 1 0 1 0 0
0 1 1 1 1 0 0
2 1 0 0 0 0 2
1 0 0 0 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2
예제 출력 6
-1
예제 입력 7
5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1
예제 출력 7
4
⭕ CODE
from collections import deque
from itertools import combinations
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def bfs(a):
q = deque()
# 방문 확인
visited = [[0]*n for _ in range(n)]
# a에 있는 모든 좌표에 대해서 방문 처리
for i in a:
q.append(i)
visited[i[0]][i[1]] = 1
while q:
x,y = q.popleft()
# 상 하 좌 우 4방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 격자안에 존재하고
if 0 <= nx < n and 0 <= ny < n:
# 벽이 아니고 방문한적이 없다면
if arr[nx][ny] != 1 and visited[nx][ny] == 0:
q.append((nx,ny))
visited[nx][ny] = visited[x][y] + 1
# 빈자리를 파악하기 위한 count
count = 0
for i in range(n):
for j in range(n):
# 방문한적이 없고 빈칸이였거나 바이러스를 놓을 수 있는 칸이였다면
if visited[i][j] == 0 and (arr[i][j] == 0 or arr[i][j] == 2):
count += 1
# 시간초와 빈자리 return
return visited[x][y] - 1,count
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
virus = []
for i in range(n):
for j in range(n):
if arr[i][j] == 2:
virus.append((i,j))
# m개의 바이러스 조합
all_virus = list(combinations(virus,m))
result = 10000
for i in all_virus:
# 시간과 빈자리
time,count = bfs(i)
# 빈자리가 없고 시간이 더 작다면 작은것으로 갱신
if time < result and count == 0:
result = time
# 불가능하다면
if result == 10000:
print(-1)
else:
print(result)✏️ Comment
모든 조합을 완전탐색해서 푸는 문제였다. 마지막에 빈자리를 체크하면서 바이러스를 놓을 수 있는 공간 또한 빈자리라는 조건을 주지 않아서 97% 쯤에서 틀렸습니다가 나와 사람들의 반례를 찾아보니 그 경우에 틀렸다.
- 조건을 잘 확인하자