[백준 Python] 14502번 연구소 (BFS)

728x90

백준 14502번 연구소 (BFS)

1. 문제

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

문제 설명

연구소에서 바이러스가 유출되었고, 바이러스의 확산을 막기 위해 벽을 3개 세워야 한다. 연구소는 N x M 크기의 격자로 주어지며,

0: 빈 칸
1: 벽
2: 바이러스
으로 이루어져 있다.

바이러스는 상하좌우로 인접한 빈 칸(0)으로만 퍼져나갈 수 있다. 벽을 세울 수 있는 모든 경우의 수를 탐색해서, 안전 영역(0)의 최대 크기를 구하는 것이 목표이다.

2. 풀이

문제 해결 접근 방법

벽 세우기
- 빈 칸(0) 중에서 3개의 위치를 선택하여 벽을 세운다.
- 이때, itertools.combinations()를 사용하여 모든 경우의 수를 탐색한다.
바이러스 퍼뜨리기 (BFS 사용)
- 바이러스는 상하좌우로 퍼지며, deque를 이용한 BFS 방식으로 구현한다.
- 탐색할 때마다 연구소 상태가 변하므로, 원본 데이터를 손상시키지 않기 위해 deepcopy()로 복사하여 사용한다.
안전 영역 계산하기
- 모든 바이러스가 퍼진 후, 남아 있는 빈 칸(0)의 개수를 세어 안전 영역의 크기를 계산한다.

3. 코드 구현

import sys
from itertools import combinations
from collections import deque
import copy

input = sys.stdin.readline

dr = [1, -1, 0, 0]  # 아래, 위, 오른쪽, 왼쪽


# 바이러스 퍼뜨리기 (BFS)
def bfs(lab, n, m):
    que = deque()
    temp_lab = copy.deepcopy(lab)  # 연구소 복사본 생성

    for i in range(n):
        for j in range(m):
            if temp_lab[i][j] == 2:  # 바이러스 발견 시 큐에 추가
                que.append((i, j))

    while que:
        r, c = que.popleft()

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]

            if 0 <= nr < n and 0 <= nc < m and temp_lab[nr][nc] == 0:
                temp_lab[nr][nc] = 2  # 바이러스 퍼뜨리기
                que.append((nr, nc))

    # 안전 영역 크기 계산
    safe_area = sum(row.count(0) for row in temp_lab)
    return safe_area


# 입력 받기
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]

# 빈 칸 위치 찾기
empty_space = [(i, j) for i in range(n) for j in range(m) if lab[i][j] == 0]
max_safe_area = 0


# 벽을 세울 수 있는 모든 조합을 탐색
for walls in combinations(empty_space, 3):
    for r, c in walls:  # 벽 세우기
        lab[r][c] = 1

    # 바이러스 퍼뜨리기 & 안전 영역 계산
    safe_area = bfs(lab, n, m)
    max_safe_area = max(max_safe_area, safe_area)

    for r, c in walls:  # 원상복구
        lab[r][c] = 0


# 결과 출력
print(max_safe_area)

💡 코드 설명 & 이해 포인트

1. 배열 복사

BFS 함수에서는 바이러스가 퍼지는 시뮬레이션을 진행한다.
lab을 직접 변경하면 다음 조합을 시험할 때 문제가 되므로, 원본은 변경하지 않기 위해 copy.deepcopy()로 복사하여 사용한다.
이 과정은 특히 탐색 과정에서 발생하는 모든 변경 사항을 원본과 분리하여 관리하기 위한 방법이다.

1) 깊은 복사

deepcopy() 사용은 메모리와 시간이 많이 소모된다. 이 문제는 크기가 작아서 괜찮지만, 큰 경우라면 다른 방법이 필요하다.
예를 들어, 벽을 세운 위치만 원상복구하는 현재 방식처럼 일부만 복구하는 방법을 고려할 수 있다.

2) 얕은 복사

다음과 같이 리스트 컴프리헨션으로 얕은 복사를 활용하면, 깊은 복사처럼 동작하지만 deepcopy를 사용하지 않아도 되고 속도도 더 빠르다.

temp_lab = [row[:] for row in lab]  # deepcopy 대신 얕은 복사 활용 (속도 더 빠름)

2. 바이러스가 벽으로 막히는 방식

바이러스가 퍼지는 부분은 bfs() 함수에서 이뤄진다.
if 0 <= nr < n and 0 <= nc < m and temp_lab[nr][nc] == 0: 조건으로 빈 칸(0)에만 전염될 수 있도록 한다.
만약 벽(1)이 있는 경우, 이 조건에서 걸러지기 때문에 전파되지 않는다.

4. 결과

얕은복사로 푼 게 1536ms로 더 빠르다.