[백준 / Python] 17142번 : 연구소 3

문제 링크:

문제 이해

---

• N×N 크기의 연구소에서 M개의 바이러스를 활성화시켜 모든 빈 칸에 퍼뜨리는 문제.
• 연구소는 빈 칸(0), 벽(1), 비활성 바이러스(2)로 구성됨.
• 활성 상태의 바이러스는 상하좌우로 1초에 한 칸씩 확산되며, 비활성 바이러스를 만나면 활성화시킴.
• M개의 바이러스를 활성화시켜 모든 빈 칸에 퍼뜨리는 최소 시간을 구하는 문제.
  • 벽으로는 바이러스가 퍼지지 않음.
  • 모든 빈 칸에 퍼뜨릴 수 없으면 -1 출력.
• 입력: 연구소 크기 N(4 ≤ N ≤ 50), 바이러스 개수 M(1 ≤ M ≤ 10).
• 출력: 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간, 불가능하면 -1.
• 최종 목표: 최소 시간 계산
• 중간 과정:
  • 바이러스의 확산 시뮬레이션 (상하좌우 이동)
  • 벽과 비활성 바이러스에 따른 확산 처리

해결 전략

---

1. 배열(격자)에서 바이러스 위치 찾기(for, for)
2. 바이러스 중에 M개 조합 DFS

3. 각 바이러스의 위치에서 for문으로 4방으로 DFS 하면서 dist 채움 → Max구하기

   바이러스가 퍼질때 주의할 것 1) 벽 2) 지나온 곳, 나보다 작은 수 3) N x N 넘어가는 것 4) * 표시 바이러스

구현 코드, 풀이

---

import collections
from collections import deque

  #  상  하  좌  우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def solution(virus, lab, M):
    def dfs(start, elements, M):
        if M == 0:
            combination.append(elements[:])
            return
        for i in range(start, num_virus):
            elements.append(i)
            dfs(i+1, elements, M-1)
            elements.pop()

    num_virus = len(virus)
    combination = []
    dfs(0, [], M)

    max_second = []
    for idx, c in enumerate(combination):
        tmp_virus = [i for i in range(num_virus)]
        dist = [[-2] * N for _ in range(N)]
        q = deque([])

        for v in c:
            vx, vy = virus[v]
            dist[vx][vy] = 0
            tmp_virus.remove(v)
            q.append((vx, vy, 1))

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

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

                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                elif lab[nx][ny] == 1:
                    dist[nx][ny] = -1
                    continue
                elif dist[nx][ny] == 0:
                    continue
                elif dist[nx][ny] != -2 and dist[nx][ny] < cnt:
                    continue
                else:
                    dist[nx][ny] = cnt
                    q.append((nx, ny, cnt+1))

        # 비활성 바이러스가 마지막 원소인지 점검
        for t in tmp_virus:
            tx, ty = virus[t]
            dist[tx][ty] = 0

        if min([min(m) for m in dist]) == -2:    # 전체를 채울 수 없을 때
            max_second.append(-1)
        else:
            max_second.append(max([max(m) for m in dist]))

    print(min(max_second))

if __name__ == '__main__':

    N, M = map(int, input().split())
    lab = [list(map(int, input().split())) for _ in range(N)]
    
    virus = []
    for i in range(N):
        for j in range(N):
            if lab[i][j] == 2:
                virus.append((i, j))

    solution(virus, lab, M)

• main 블록:
  • 초기 입력을 받고, 실험실의 크기(NxN)와 활성화할 바이러스의 수(M)를 입력받음.
  • 실험실 정보(lab)를 입력받고, 바이러스의 위치를 virus 리스트에 저장.
  • solution 함수(2.)를 호출하여 바이러스가 퍼지는 데 걸리는 최소 시간을 계산하고 출력함.
• solution 함수:
  • dfs 함수(3.)를 호출하여 M개의 바이러스를 선택하는 모든 경우의 수를 구함.
  • combination 리스트에 저장된 각 바이러스 조합에 대해 BFS(너비 우선 탐색)를 수행하여 해당 조합에서 바이러스가 퍼지는 데 걸리는 시간을 계산.
  • 각 조합에서의 결과를 저장한 후, 가장 적은 시간을 기록하고 이를 출력.
• dfs 함수:
  • M개의 바이러스를 선택하는 조합을 구하는 함수.
  • start 인덱스에서 시작하여 M개의 바이러스를 선택하기 위해 재귀 호출을 사용. 선택된 바이러스는 elements 리스트에 저장됨.
  • M개의 바이러스를 모두 선택했을 경우, combination 리스트에 추가하고 함수 종료.
• BFS를 이용한 바이러스 퍼뜨리기:
  • 각 조합에 대해 큐(q)에 선택된 바이러스의 위치를 넣고 BFS를 시작함.
  • 상하좌우 4방향으로 바이러스를 퍼뜨리며, 이동한 거리를 dist 리스트에 기록함.
  • 벽(1)이나 이미 방문한 곳은 건너뜀.
  • 바이러스를 다 퍼뜨린 후, 실험실이 전부 감염됐는지 확인하고, 감염될 수 없는 곳이 있을 경우 해당 조합은 무효 처리함.
• 최소 시간 계산:
  • 각 조합에 대해 바이러스를 다 퍼뜨리는 데 걸린 시간을 계산하고, max_second 리스트에 저장.
  • 모든 조합 중에서 가장 적은 시간을 가진 값을 선택해 출력.