백준 14502번: 연구소 (Python)

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

14502번: 연구소

접근

빈 공간(0) 중에서 3곳을 선택하여 벽으로 지정하고, 바이러스(2)에서 시작하여 바이러스가 얼마나 많은 공간을 침범하는지를 카운트 해주는 방법으로 계산할 수 있었다.

벽으로 막을 지점을 선정하는 것은 3중 for문을 이용하여 모든 지점을 고려해주었고, 바이러스가 감염되는 경로는 bfs 알고리즘을 이용하여  구하였다.

벽으로 막을 공간을 계속 바꿔주면서 바이러스 감염 수를 카운트 해주고, 처음 빈 공간의 개수에서 벽으로 바꾸는 공간(3)과 바이러스가 침범한 공간을 빼서 안전 구역의 개수를 계산하였다.

그리고 계산을 빠르게 하기 위해서 새로 계산할 때 기존 바이러스 개수보다 커지면 계산을 중단하는 방식으로 계산을 빠르게 진행할 수 있었다.

코드

from collections import deque
from copy import deepcopy

N, M = map(int, input().split())
matrix = []
start = []
zero_list = []
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 2:
            start.append((i, j))
        if tmp[j] == 0:
            zero_list.append((i, j))
    matrix.append(tmp)
rc = [1, 0, -1, 0]
cc = [0, 1, 0, -1]


def solve(matrix):
    # 빈 공간 중 3개를 선택하여 벽으로 막고, 바이러스를 카운트 하는 bfs 계산을 진행하도록 하는 함수
    min_virus = float("inf")  # 최소 바이러스 감염 수를 저장
    for i in range(len(zero_list) - 2):
        matrix[zero_list[i][0]][zero_list[i][1]] = 1
        for j in range(i + 1, len(zero_list) - 1):
            matrix[zero_list[j][0]][zero_list[j][1]] = 1
            for k in range(j + 1, len(zero_list)):
                matrix[zero_list[k][0]][zero_list[k][1]] = 1
                board = deepcopy(matrix)
                res = bfs(board, min_virus)
                min_virus = min(res, min_virus)
                matrix[zero_list[k][0]][zero_list[k][1]] = 0
            matrix[zero_list[j][0]][zero_list[j][1]] = 0
        matrix[zero_list[i][0]][zero_list[i][1]] = 0
    return min_virus


def bfs(board, old_min):
    # bfs 알고리즘을 이용하여 바이러스가 침범한 공간의 수를 카운트
    queue = deque([])
    cnt_virus = 0
    for virus in start:
        queue.append(virus)
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r + rc[i], c + cc[i]
            if 0 <= nr < N and 0 <= nc < M and board[nr][nc] == 0:
                # 바이러스에서 이동한 공간이 연구소를 벗어나지 않으며 빈 공간이면 바이러스에 감염되었다고 표시
                board[nr][nc] = 2
                queue.append((nr, nc))
                cnt_virus += 1
        if cnt_virus >= old_min:
            # 바이러스를 카운트 하는 중에 기존 최소 바이러스 개수를 초과할 경우 계산을 중단
            return float("inf")
    return cnt_virus


ans = solve(matrix)
# 처음의 빈 공간 수 - 벽으로 막은 빈공간 수(3) - 바이러스 감염 수 = 안전 지대 개수
print(len(zero_list) - 3 - ans)

더 생각해 볼 것?

벽으로 막을 공간이 3개로 지정되어 있어 3중 for문을 이용하여 간단하게 풀었는데, 개수가 문제마다 새로 지정된다면 벽을 지정하는 것 또한 dfs 알고리즘 등을 이용하여 풀어야 할 것 같다. 공부를 위해 그렇게 수정하는 방법을 생각해 보아야 겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!