백준 14502

 

코드

from collections import deque
from copy import deepcopy
import itertools

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

# 빈 칸의 좌표와 바이러스의 좌표를 구합니다.
empty_spaces = []
virus_spaces = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            empty_spaces.append((i, j))
        elif graph[i][j] == 2:
            virus_spaces.append((i, j))

# BFS로 바이러스가 퍼지는 영역을 계산하는 함수를 정의합니다.
def bfs(graph):
    queue = deque(virus_spaces)
    while queue:
        x, y = queue.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                graph[nx][ny] = 2
                queue.append((nx, ny))

# 안전 영역의 크기를 계산하는 함수를 정의합니다.
def count_safe(graph):
    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                count += 1
    return count

# 모든 조합에 대해 안전 영역의 크기를 계산하여 최댓값을 구합니다.
max_safe = 0
for comb in itertools.combinations(empty_spaces, 3):
    new_graph = deepcopy(graph)
    for x, y in comb:
        new_graph[x][y] = 1
    bfs(new_graph)
    max_safe = max(max_safe, count_safe(new_graph))

print(max_safe)