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

💬 주소: 

17142번: 연구소 3

💬 문제:

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

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

 

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

 

💬 코드:

from collections import deque
from itertools import combinations


def activate(virus):
    dist = [[-1] * N for _ in range(N)]
    queue = deque(virus)
    for v in virus:
        x, y = v
        dist[x][y] = 0
    max_dist = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in direction:
            nx, ny = x+dx, y+dy
            if 0 <= nx < N and 0 <= ny < N and lab[nx][ny] != 1 and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y]+1
                if lab[nx][ny] == 0:
                    max_dist = max(max_dist, dist[nx][ny])
                queue.append([nx, ny])

    if list(sum(dist, [])).count(-1) == list(sum(lab, [])).count(1):
        times.append(max_dist)

N, M = map(int,input().split())
lab = [list(map(int,input().split())) for _ in range(N)]
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

virus = deque()
times = []
for i in range(N):
    for j in range(N):
        if lab[i][j] == 2:
            virus.append([i, j])

for case in combinations(virus, M):
    activate(case)

print(min(times) if times else -1)

 

딕셔너리로 풀려고 하다가 계속 DFS로 구현해서 망한 문제다... 최단 시간을 구해야 하니 BFS를 써야 하는데😥

이제 괜히 다르게 구현하지 말고 최단 경로/시간 같은거 구하는 문제는 바로 BFS써서 풀어야겠다. 

 

아래는 DFS 시간 초과 나온 코드🙄

from itertools import combinations

# 입력 처리
N, M = map(int, input().split())
lab, virus = dict(), list()
for i in range(N):
    state = input().split()
    for j in range(N):
        if state[j] == '2':
            virus.append((i, j))
        if state[j] == '0':
            lab[(i, j)] = 0


# 활성화
def activate(sample, locs, time):
    if sample.values() and all(v != 0 for v in sample.values()):
        times.append(max(sample.values()))
        return
    if all(loc[0]<0 or loc[1]<0 or loc[0]>N-1 or loc[1]>N-1 for loc in locs):
        return
    if times and time >= min(times):
        return

    next = []
    for loc in locs:
        x, y = loc
        for dx, dy in direction:
        	nx, ny = x+dx, y+dy
          if (nx, ny) in sample and sample[(nx, ny)] == 0:
              sample[(nx, ny)] = time
              next.append((nx, ny))
    activate(sample, next, time+1)

times = []
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for case in combinations(virus, M):
    if all(v == 1 for v in dict(lab).values()):
        times.append(0)
        break
    activate(dict(lab), case, 1)

print(times[-1] if times else -1)