[코드트리] 바이러스 백신 (python)

🔗 문제 링크

https://www.codetree.ai/frequent-problems/vaccine-for-virus/description

https://www.acmicpc.net/problem/17142 (백준 - 연구소 3)

👩🏻‍💻 코드

import sys
from collections import deque

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

N, M = map(int, sys.stdin.readline().rstrip().split())
maps = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
hospital_comb = []
answer = INF


def dfs(hospital_list, pick_list, idx):
    if idx == len(hospital_list):
        if len(pick_list) == M:
            hospital_comb.append(pick_list[:])
        return

    pick_list.append(hospital_list[idx])
    dfs(hospital_list, pick_list, idx + 1)
    pick_list.pop()
    dfs(hospital_list, pick_list, idx + 1)


def bfs(hospital_list):
    global answer
    q = deque([])
    visited = [[False] * N for _ in range(N)]
    time_maps = [[0] * N for _ in range(N)]

    for h in hospital_list:
        q.append((h[0], h[1], 0))
        visited[h[0]][h[1]] = True

    while q:
        x, y, cnt = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if maps[nx][ny] == 0 or maps[nx][ny] == -2:
                    q.append((nx, ny, cnt + 1))
                    visited[nx][ny] = True
                    time_maps[nx][ny] = cnt + 1

    time = 0
    for i in range(N):
        for j in range(N):
            if maps[i][j] == 0 and time_maps[i][j] == 0:
                return
            if maps[i][j] == 0:
                time = max(time, time_maps[i][j])
    answer = min(answer, time)


hospital = []
for i in range(N):
    for j in range(N):
        if maps[i][j] == 2:
            hospital.append((i, j))
            maps[i][j] = -2
        if maps[i][j] == 1:
            maps[i][j] = -1

dfs(hospital, [], 0)

for i in range(len(hospital_comb)):
    bfs(hospital_comb[i])

print(-1) if answer == INF else print(answer)

📝 정리

1. 병원: -2, 벽: -1로 변경하기
2. dfs(조합)으로 M개의 병원 고르기
3. 각 조합마다 bfs를 사용해 바이러스 퍼트려 보기
   3-1. time_maps에 시간 기록
   3-2. 도달하지 못한 곳이 있다면 return
   3-3. 바이러스를 모두 잡았으면 time에 총 시간 저장
4. answer에 최소 time 저장

💡기억해야 할 것

• dfs에서 return 할 경우, None이 나올 수 있으므로 주의하자.
• copy를 사용하고 싶을 땐 deepcopy를 사용하자.

import copy
b = copy.deepcopy(a)

참고했던 블로그
https://velog.io/@munang/%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC-Python-None-%EB%A6%AC%ED%84%B4%ED%95%98%EB%8A%94-%EA%B2%BD%EC%9A%B0-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-None-%EB%A6%AC%ED%84%B4 (return None)
https://crackerjacks.tistory.com/14 (deepcopy)