0520_백준 17142번 : 연구소 3 / BFS 알고리즘/ Python

[문제 접근]

- BFS(너비우선탐색)으로 최단 시간 구하는 문제(바이러스가 확산되며 1씩 증가하는 형태)

- itertools 모듈에서 chain 불러오기, list(sum(arr, [ ])) 보다 list(chain(*arr))이 속도는 더 빠름.

- 처음에는 바이러스 위치를 정하는 조합을 함수로 구현하려다가 실패한 후, 결국 itertools 모듈 콤비네이션을 활용함

- deepcopy로 배열을 똑같이 만들어도 되나, 이번 코드에서는 새로운 배열을 하나 만들었다.

- 문법체크✔

① print(min(res) if res else -1) : res에 값이 있으면 (True) ->min(res) 출력, 값이 없다면(False) -> -1 출력

② 2차원 배열 1차원 리스트로 합치기 : list(sum(arr,[]))  또는 list(chain(*arr))

 

[코드 구현] 

from collections import deque
from itertools import combinations as combi
from itertools import chain

def bfs(virus):
    temp = [[-1]*n for _ in range(n)]
    q = deque()
    max_v = 0
    # 바이러스 위치(시작점)를 0으로 바꾸기
    for i in virus:
        q.append(i)
        temp[i[0]][i[1]] = 0

    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                # 기존 사무실 배열에서 벽이 아닌 지도 확인
                if arr[nx][ny] != 1 and temp[nx][ny] == -1:
                    # 바이러스가 퍼질 수록 시간은 1씩 증가
                    temp[nx][ny] = temp[x][y] + 1
                    if arr[nx][ny]==0:
                        max_v = max(max_v, temp[nx][ny])
                    q.append([nx, ny])

    total1 = list(chain(*temp))
    total2 = list(chain(*arr))
    # 나머지 방과 벽의 개수가 동일한지 확인한 후 결과리스트에 넣기
    if total1.count(-1) == total2.count(1):
        res.append(max_v)

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [-1,1,0,0], [0,0,-1,1]
res = []

# 바이러스 위치가 담긴 리스트 만들기
virus_lst = deque()
for i in range(n):
    for j in range(n):
        if arr[i][j] == 2:
            virus_lst.append([i, j])

for virus in combi(virus_lst, m):
    bfs(virus)
print(min(res) if res else -1)

 

[문제 출처]

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

17142번: 연구소 3