[Python/파이썬] 백준 17142 - 연구소3

문제 설명

 

 

입력과 출력

 

입출력 예제

17142번: 연구소 3

 

---

풀이 코드

이 문제는 삼성 SW 기출문제에 출제된 문제라고 한다.

삼성 SW 문제들이 좀 문제를 이해하는데 어렵지 않나 한다. 이문제도 마찬가지로 문제를 이해하기가 좀 어려웠다;

 

이 문제를 푸는 방식에 대해 설명하자면

바이러스 M개를 활성화 해야하므로 파이썬의 combinations를 이용해 활성화할 바이러스 M개의 위치의 조합들을 구하여 해당 좌표들을 큐에 넣고 탐색하도록 하였다.

그리고 그 활성화된 바이러스 좌표들을 시작으로 빈칸 이면 바이러스를 퍼트리고

비활성화된 바이러스는 바이러스를 활성화시키기 때문에 비활성화 바이러스를 만난 경우에도 조건문에 추가하였다.

 

그리고 중요한점으로 모든 빈 칸들을 모두 감염시켜야하는데

이 부분을 체크하기 위해  blank라는 주어진 2차원 배열에서 0 ( 빈칸 ) 의 수를 담는 변수를 선언하여 담았다.

그리고 빈 칸을 만나 바이러스를 퍼트린 후에 blank를 1 감소시켜 0이 될 때 동안 탐색하도록 하였다.

 

정답 코드

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

N, M = map(int, input().split()) # 연구소의 크기, 바이러스의 개수

laboratory = [list(map(int, input().split())) for _ in range(N)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

def bfs(virus, blank):
    q = deque()
    visited = [[False] * N for _ in range(N)]
    time = 0

    for i, j in virus:
        q.append((i, j, 0))
        visited[i][j] = True

    while q:
        x, y, cnt = q.popleft()

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

            if 0 <= nx < N and 0 <= ny < N:
                # 빈 칸을 만난 경우
                if laboratory[nx][ny] == 0 and not visited[nx][ny]:
                    q.append((nx, ny, cnt + 1))
                    visited[nx][ny] = True
                    blank -= 1
                    time = max(time, cnt + 1)
                # 비활성화 바이러스를 만난 경우
                if laboratory[nx][ny] == 2 and not visited[nx][ny]:
                    q.append((nx, ny, cnt + 1))
                    visited[nx][ny] = True
    
    if blank != 0:
        return 1e9
    else:
        return time

blank = 0
virus_pos = []
for x in range(N):
    for y in range(N):
        if laboratory[x][y] == 2:
            virus_pos.append((x, y))
        if laboratory[x][y] == 0:
            blank += 1

result = 1e9
for virus in combinations(virus_pos, M):
    result = min(result, bfs(virus, blank))

if result != 1e9:
    print(result)
else:
    print(-1)