백준 14502 - 연구소 (파이썬)

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

풀이

이 문제는 BFS와 완전 탐색을 조합하여 해결하는 문제이다.

문제에서는 연구소에서 벽을 3개 세우는 모든 경우의 수를 고려하고, 이후 바이러스가 퍼지는 과정을 BFS로 시뮬레이션하여 안전 영역의 최대 크기를 구하는 방식으로 해결한다.

사용한 해결 전략은 다음과 같다.

1. 연구소에서 빈칸 (0)의 좌표를 찾는다.
2. 빈칸 중 3곳을 선택하여 벽을 세운다. (여기서 필자는 combinations()를 통해 조합을 구함)
3. BFS를 이용해서 바이러스를 퍼뜨린다.
4. 바이러스가 퍼진 후 남은 안전 영역(0)을 계산한다.
5. 벽을 세우기 전 상태로 되돌린다. (백트래킹)
6. 가장 큰 안전 영역 값을 저장하여 출력한다.

cells = [(i, j) for i in range(N) for j in range(M) if B[i][j] == 0]

일단 연구소의 모든 빈 칸 위치를 리스트로 저장한다.

for combination in combinations(cells, 3):

combinations(celss, 3) 을 이용해 빈 칸 중 3개를 선택하는 모든 경우를 탐색한다.

for row, col in combination:
    B[row][col] = 1  # 벽 세우기

선택한 3개의 위치에 벽을 세운다.

visit = [[False] * M for _ in range(N)]
queue = deque()

for i in range(N):
    for j in range(M):
        if B[i][j] == 2:
            queue.append((i, j))
            visit[i][j] = True

queue에 초기 바이러스 위치를 넣고 BFS를 준비한다.

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

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

        if 0 <= nr < N and 0 <= nc < M and not visit[nr][nc] and B[nr][nc] == 0:
            queue.append((nr, nc))
            visit[nr][nc] = True

상하좌우 방향으로 바이러스를 확산하고, visit[nr][nc] = True 를 통해 방문 처리를 진행한다.

safe = 0
for i in range(N) :
    for j in range(M) :
        if B[i][j] == 0 and not visit[i][j] :
            safe += 1

safe 즉 안전영역을 0으로 초기화 하고, 안전영역이면서 방문하지 않았을 경우의 칸을 계산한다.

max_safe = max(max_safe, safe)

for row, col in combination :
    B[row][col] = 0

다시 벽을 원래 상태로 되돌려서 다른 경우의 수를 탐색하도록 진행한다.

시간복잡도를 분석하면 다음과 같다.

• combinations(cells, 3): 최대 3!(64−3)!64!≈41664 (최대 64개의 빈칸)
• BFS: 최대 O(NM) ≈ 64
• 최악의 경우: O(41664×64) ≈ 2.6 × 10^6 → 충분히 가능

코드

# 백준 14052 - 연구소
# 분류 : BFS, DFS

from collections import deque
from itertools import combinations

N, M = map(int, input().split())
B = [[] for _ in range(N)]

for i in range(N) :
    B[i] = list(map(int, input().split()))

cells = [(i ,j) for i in range(N) for j in range(M) if B[i][j] == 0]

max_safe = 0

for combination in combinations(cells, 3) :
    for row, col in combination :
        B[row][col] = 1
    
    # BFS
    visit = [[False] * M for _ in range(N)]
    queue = deque()

    for i in range(N) :
        for j in range(M) :
            if B[i][j] == 2 :
                queue.append((i, j))
                visit[i][j] = True
    
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    while len(queue) != 0 :
        r, c = queue.popleft()

        for i in range(4) :
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or N <= nr or nc < 0 or M <= nc :
                continue
            if B[nr][nc] == 1 :
                continue
            if not visit[nr][nc] :
                queue.append((nr, nc))
                visit[nr][nc] = True
    
    safe = 0
    for i in range(N) :
        for j in range(M) :
            if B[i][j] == 0 and not visit[i][j] :
                safe += 1

    max_safe = max(max_safe, safe)

    for row, col in combination :
        B[row][col] = 0

print(max_safe)