[Python] 백준 <14502-연구소>

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

 

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

# 바이러스 전이
def spread_virus(lab):
    q = deque()
    for i in range(N):
        for j in range(M):
            if lab[i][j] == 2:
                q.append((i, j))
    
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x + dx, y + dy
            # 전이하는 곳에 벽이 없고 0이면 전이
            if 0 <= nx < N and 0 <= ny < M and lab[nx][ny] == 0:
                lab[nx][ny] = 2
                q.append((nx, ny))

N, M = map(int, input().split(" "))
virus_map = []
for _ in range(N):
    virus_map.append(list(map(int, input().split(" "))))

# 빈 공간 좌표 저장
empty = []
for i in range(N): 
    for j in range(M):
        if virus_map[i][j] == 0:
            empty.append((i, j))

dap = 0
# 벽 3개 조합으로 세우기
for walls in combinations(empty, 3):
    # 리스트 복사
    lab = copy.deepcopy(virus_map)
    
    # 벽 세우기
    for x, y in walls:
        lab[x][y] = 1

    # 바이러스 전이
    spread_virus(lab)

    # 안전 영역 계산
    safe = 0
    for i in lab:
        for j in i:
            if j == 0:
                safe += 1
    dap = max(dap, safe)

print(dap)