백준 17142번 | 연구소 3 - python

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

17142번: 연구소 3

 

문제

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

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 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 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 *

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

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
* - 3 2 3 4 *

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

입력

첫째 줄에 연구소의 크기 N(4 ≤ 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

4

예제 입력 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

4

예제 입력 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

0

 

 

 

이 문제는 combinations를 이용해서 문제를 푸는 것인데

itertools의 combinations를 사용하기 않고 문제를 풀었다.

이유는 삼성 환경에서는 사용을 못하기 때문에 미리 적응 해보기 위해서다

조합을 구한뒤 구해진 바이러스를 통해 BFS를 진행해서 남은 0이 없는 경우만 색출해서

값을 비교하는 식으로 문제를 풀었다

 

아래의 코드를 보자

 

import sys
from collections import deque

input = sys.stdin.readline


# 바이러스가 퍼지는 과정
def Diffusions(virus, boards, visited, N, zero):
    value, cnt = 0, 0
    # 선택된 바이러스 자리에 초기값 0을 입력
    for r, c in virus:
        visited[r][c] = 0
    while virus:
        row, col = virus.popleft()
        for j, i in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
            nj, ni = row + j, col + i
            # 벽이 아닌 부분에 확산을 진행
            if 0 <= nj < N and 0 <= ni < N and boards[nj][ni] != 1 and visited[nj][ni] == -1:
                visited[nj][ni] = visited[row][col] + 1
                virus.append([nj, ni])
                # 값이 0이면 최댓값 업데이트 진행, 2인 경우에는 그냥 활성화만 되기 때문에 업데이트를 하지 않는다.
                if not boards[nj][ni]:
                    # 0의 갯수를 세는 cnt + 1 해준다
                    cnt += 1
                    value = max(value, visited[nj][ni])

    # cnt가 초기 0의 갯수인 zero와 같다면 value 반환, 아니면 무한대값 반환
    if cnt == zero:
        return value
    else:
        return float('inf')


# M개를 뽑아내는 combinations 과정
def SelectM(i, k, N, M, boards, viruses, arr, zero):
    global answer
    if i == M:
        visited = [[-1 for _ in range(N)] for _ in range(N)]
        
        # 확산이 다 된 값과 answer를 비교하여 최솟값 도출, Diffusion 진행
        answer = min(answer, Diffusions(deque(arr), boards, visited, N, zero))
    else:
        for j in range(k, len(viruses)):
            if viruses[j] not in arr:
                arr.append(viruses[j])
                SelectM(i + 1, j, N, M, boards, viruses, arr, zero)
                arr.pop()


answer = float('inf')
n, m = map(int, input().split())
viruses, boards, zero = [], [], 0
# 입력을 받으면서 바이러스의 위치와 0의 개수 업데이트
for row in range(n):
    ls = list(map(int, input().split()))
    for col in range(n):
        if ls[col] == 2:
            viruses.append([row, col])
        if not ls[col]:
            zero += 1
    boards.append(ls)

# combinations 시작
SelectM(0, 0, n, m, boards, viruses, [], zero)
# 만약 answer가 float('inf')이면 -1 아니면 answer 출력
if answer == float('inf'):
    print(-1)
else:
    print(answer)