[ 백준 17142 ] 연구소 3 - Python

문제 보기

BFS 문제이다.

연구소의 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구하면 된다.

 

바이러스 후보 위치 파악

모든 빈칸에 바이러스가 있도록 하기 위해서는 바이러스를 놓을 수 있는 위치를 구해야 한다. 따라서 2차원 배열을 탐색하면서 값이 2인 곳의 위치를 따로 저장한다.

 

조합을 활용하여 모든 경로 탐색

바이러스는 후보 위치 중 최대 m개까지 놓을 수 있다. 파이썬은 itertools의 combination을 통해서 후보 위치 중 m개를 놓는 모든 경우를 쉽게 파악할 수 있다.

 

BFS를 이용한 탐색

최종적으로 선택된 바이러스는 상, 하, 좌, 우를 탐색하면서 퍼져나간다. 모든 경우에 대해서 bfs 탐색을 진행한 후 가장 적은 시간에 모든 빈칸에 바이러스를 퍼트린 시간을 출력하면 된다. 만약 바이러스를 어떻게 놓아도 모든 빈칸에 바이러스를 퍼트릴 수 없는 경우에는 -1을 출력한다.

 

import copy
from itertools import combinations
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = 1e9


def change_array(array, location):  # 바이러스 놓기
    for i, j in location:
        array[i][j] = "*"
    return array


def bfs(array):
    global result
    q = deque()
    count = 0  # 빈칸의 개수
    for i in range(n):
        for j in range(n):
            if array[i][j] == "*":
                q.append((i, j, 0))
            elif array[i][j] == 0:
                count += 1

    while q:
        x, y, cnt = q.popleft()
        if cnt > result:
            return
        if count == 0:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if array[nx][ny] == 0:
                    array[nx][ny] = -(cnt + 1)
                    q.append((nx, ny, cnt + 1))
                    count -= 1
                elif array[nx][ny] == 2:
                    array[nx][ny] = -(cnt + 1)
                    q.append((nx, ny, cnt + 1))
                elif array[nx][ny] != "*" and array[nx][ny] < -(cnt + 1):
                    array[nx][ny] = -(cnt + 1)
                    q.append((nx, ny, cnt + 1))
                elif array[nx][ny] == "*":
                    array[nx][ny] = -(cnt + 1)
                    q.append((nx, ny, cnt + 1))

    # 모두 바이러스로 바꼈는지 확인
    answer = 0
    for i in range(n):
        for j in range(n):
            if array[i][j] == 0:
                return -1
            elif array[i][j] != "*" and array[i][j] < 0:
                answer = max(answer, abs(array[i][j]))

    result = min(result, answer)


if __name__ == "__main__":
    n, m = map(int, input().split())  # 연구소의 크기, 바이러스의 개수
    array = [list(map(int, input().split())) for _ in range(n)]

    # 바이러스를 놓을 수 있는 위치 탐색
    location = []
    for i in range(n):
        for j in range(n):
            if array[i][j] == 2:
                location.append((i, j))

    # 모든 경우 bfs 탐색
    result = INF
    for data in list(combinations(location, m)):
        arr = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                arr[i][j] = array[i][j]
        arr = change_array(arr, data)
        bfs(arr)

    # 출력
    if result == INF:
        print(-1)
    else:
        print(result)