[백준 🥇3] 17142번 연구소 3 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

삼성 코테에서 itertools를 못쓴다는 말이 있어서 DFS와 BFS를 사용해 풀어봤다

from collections import deque

n, m = map(int, input().split())
room = []
for _ in range(n):
    room.append(list(map(int, input().split())))

virus = []
for i in range(n):
    for j in range(n):
        if room[i][j] == 2:
            virus.append([i, j])

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

# 바이러스를 퍼뜨리는 최소 시간 구하기 
def bfs(active):
    q = deque()
    dist = [[-1] * n for _ in range(n)]   # 각 칸에 바이러스를 퍼뜨리는 데 걸리는 시간
    for y, x in active:
        q.append([y, x])
        dist[y][x] = 0

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and dist[ny][nx] == -1:
                if room[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x] + 1
                    q.append([ny, nx])
                if room[ny][nx] == 2:
                    dist[ny][nx] = dist[y][x] + 1
                    q.append([ny, nx])

    rst = 0
    for i in range(n):
        for j in range(n):
            if room[i][j] == 0:
                if dist[i][j] == -1:
                    rst = float('inf')
                    break
                else:
                    rst = max(rst, dist[i][j])
        if rst == float('inf'):
            break

    return rst

# 바이러스 중 m개 고르기 
def dfs(idx, active):
    global answer

    if len(active) == m:
        answer = min(answer, bfs(active))
    
    if idx == len(virus):
        return

    dfs(idx+1, active+[virus[idx]])
    dfs(idx+1, active)

answer = float('inf')
dfs(0, [])
if answer == float('inf'):
    print(-1)
else:
    print(answer)

3️⃣ 풀이

이 문제에서 어려웠던 점은 비활성 바이러스를 처리하는 부분이었는데
비활성 바이러스도 활성 바이러스가 되어 바이러스를 퍼뜨릴 수 있으므로 BFS 내에서 처리를 해줘야 하며, 복제되는데 1초가 걸린다
​
대신 문제에서 요구한 답은 '모든 빈 칸'에 바이러스를 퍼뜨리는 최소 시간이므로 비활성 바이러스가 있는 모든 칸에 바이러스를 퍼뜨리지 않아도 된다
즉, 내 풀이에서 room이 0인 부분에서의 dist 리스트 값만 고려해주면 된다