9. [re] 연구소

백준

1. DFS

import sys
import copy
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

result = -sys.maxsize
virus = []
for i in range(n):
    for j in range(m):
        if board[i][j] == 2:
            virus.append((i, j))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def check(keep):
    now = 0
    for i in range(n):
        for j in range(m):
            if keep[i][j] == 0:
                now += 1
    return now


def go(x, y, keep):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and keep[nx][ny] == 0:
            keep[nx][ny] = 2
            go(nx, ny, keep)


def dfs(count):
    global result
    if count == 3:
        keep = copy.deepcopy(board)
        for x, y in virus:
            go(x, y, keep)

        result = max(result, check(keep))
        return
    
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                dfs(count + 1)
                board[i][j] = 0
    

dfs(0)
print(result)


`