[백준] 14052번 연구소

문제

연구소는 직사각형으로 n x m인 배열이 주어진다. 각 인덱스마다 3개의 값을 가진다.

0: 빈 칸
1: 벽
2: 바이러스

바이러스는 상하좌우로 확산한다. 단, 벽으로는 확산하지 못한다.
빈칸에 추가적으로 벽을 세워 바이러스 확산을 최대한 막으려한다.
벽을 3개 세웠을 때 최대 크기의 안전영역을 구해라.

ex)

n, m = 7, 7
labMap = [
	[2, 0, 0, 0, 1, 1, 0],
	[0, 0, 1, 0, 1, 2, 0],
	[0, 1, 1, 0, 1, 0, 0],
	[0, 1, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 1, 1],
	[0, 1, 0, 0, 0, 0, 0],
	[0, 1, 0, 0, 0, 0, 0]
]

n, m은 최대 8의 범위를 가진다. 따라서 3개의 벽을 선택할 때의 모든 경우에 대해 BFS를 사용해도 시간을 만족할거라 생각했다.

값이 0인 빈 칸 중에 3군데를 선택해 바이러스를 끝까지 확산시키고 남아있는 안전영역의 수를 구해 항상 최대값을 가지도록 비교하기로 했다.

코드

import sys
import itertools
from collections import deque
input = sys.stdin.readline

def virusDiffusion():
    """
    바이러스 확산시키고 남아있는 안전영역의 크기를 반환
    """

    q =  deque(virusPosList)
    originEmptyPosList = []

    while q:
        cx, cy = q.popleft()

        for dx, dy in direction:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < n and 0 <= ny < m and labMap[nx][ny] == 0:
                labMap[nx][ny] = 2
                q.append((nx, ny))
                originEmptyPosList.append((nx, ny))

    # 남아있는 안전영역의 수 카운팅
    emptyPosCnt = 0
    for i in range(n):
        for j in range(m):
            if labMap[i][j] == 0:
                emptyPosCnt += 1

    # 재사용을 위한 이전상태로 돌려놓기
    for i, j in originEmptyPosList:
        labMap[i][j] = 0

    return emptyPosCnt

n, m = map(int, input().split())
labMap = [list(map(int, input().split())) for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
emptyPosList = []
virusPosList = []
answer = 0

for i in range(n):
    for j in range(m):
        if labMap[i][j] == 0:
            emptyPosList.append((i, j))
        elif labMap[i][j] == 2:
            virusPosList.append((i, j))

for selectedPosList in itertools.combinations(emptyPosList, 3):
    # 세 군데에 벽을 세움 
    for i, j in selectedPosList:
        labMap[i][j] = 1

    # 안전영역의 최대 크기
    answer = max(answer, virusDiffusion())
    
    # 재사용을 위한 이전상태로 돌려놓기
    for i, j in selectedPosList:
        labMap[i][j] = 0

print(answer)