백준 14502번 연구소

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(100000)

# 입력 받기
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

answer = 0
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def bfs():
    global answer
    # 실행 할 때마다 초기화 되어야 함
    visit = [[False] * m for _ in range(n)]

    queue = deque()
    for i in range(n):
        for j in range(m):
            # 바이러스 근원지는 방문 처리
            if graph[i][j] == 2:
                visit[i][j] = True
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny] and graph[nx][ny] == 0:
                visit[nx][ny] = True
                queue.append((nx, ny))

    safe = 0
    for i in range(n):
        for j in range(m):
            # 바이러스도 아니고 벽도 아니면서 감염되지 않은 지역 = 안전 영역
            if graph[i][j] == 0 and not visit[i][j]:
                safe += 1

    answer = max(answer, safe)


blank = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            blank.append((i, j))


def dfs(idx, count):
    # 3의 벽이 세워지면
    if count == 3:
        # 안전 영역을 계산
        bfs()
        return

    if idx == len(blank):
        return

    # 벽을 세우는 경우
    graph[blank[idx][0]][blank[idx][1]] = 1
    dfs(idx + 1, count + 1)

    # 벽을 안 세우는 경우
    graph[blank[idx][0]][blank[idx][1]] = 0
    dfs(idx + 1, count)


dfs(0, 0)
print(answer)