[백준/파이썬] 14502번 연구소 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 14502번 연구소
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

연구소 지도에서 빈 칸(0) 중 3곳에 벽을 세운 뒤, 바이러스(2)가 퍼진 결과를 시뮬레이션했을 때 안전 영역(끝까지 0으로 남는 칸)의 최댓값을 구하는 문제입니다.

코드

import sys; read=sys.stdin.readline
from collections import deque

n, m = map(int, read().split())
cells = [list(map(int, read().split())) for _ in range(n)]

emptyCells, virusCells = [], []
for i in range(n):
    for j in range(m):
        if cells[i][j] == 0: emptyCells.append((i,j))
        elif cells[i][j] == 2: virusCells.append((i,j))

wallCases = []

def backTracking(wallCase):
    if len(wallCase) >= 3:
        wallCases.append(wallCase)
        return
    for i in range(wallCase[-1]+1, len(emptyCells)+len(wallCase)-2):
        backTracking(wallCase+[i])

for i in range(len(emptyCells)-2):
    backTracking([i])

virusCellMin = 64
directions = [(-1, 0),(0, 1),(1, 0),(0, -1)]

q = deque([])
enQ = q.append
deQ = q.popleft

for wallCase in wallCases:
    q.clear()
    tmpCells = [cells[i][:] for i in range(n)]
    for virusCell in virusCells: enQ(virusCell)
    for idx in wallCase:
        tmpCells[emptyCells[idx][0]][emptyCells[idx][1]] = 1
    tmpVirusCnt = len(virusCells)

    while q:
        virus = deQ()
        for direction in directions:
            i, j = virus[0] + direction[0], virus[1] + direction[1]
            if 0 <= i < n and\
               0 <= j < m and\
               tmpCells[i][j] == 0:
                tmpCells[i][j] = 2
                enQ((i, j))
                tmpVirusCnt += 1
                if tmpVirusCnt >= virusCellMin:
                    q.clear()
                    break
                
    virusCellMin = min(tmpVirusCnt, virusCellMin)

print(len(emptyCells) - 3 - virusCellMin + len(virusCells))

설명

전형적인 조합 + BFS 시뮬레이션 문제입니다.

• 빈 칸 중 3개를 고르는 모든 경우를 백트래킹으로 생성합니다.
• 각 경우마다 임시 맵을 복사하고 바이러스 확산을 BFS로 계산합니다.
• 감염 수가 이미 현재 최솟값 이상이면 조기 중단해 시간을 줄입니다.
• 최종적으로 안전 영역 최대값을 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---