백준 - 14502 연구소

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

import copy

n = m = 0           # 지도 리스트의 NxM 크기
virus_list = []     # 바이러스(2) 위치 좌표들
arr = []            # 원본 지도 리스트
max_val = 0         # 안전영역 결과값
dx = [-1, 1, 0, 0]  # 상하좌우
dy = [0, 0, -1, 1]  #


def get_safe_area(copyed):
    safe = 0
    for i in range(n):
        for j in range(m):
            if copyed[i][j] == 0:
                safe += 1
    return safe


def spread_virus(x, y, copyed):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if copyed[nx][ny] == 0:
                copyed[nx][ny] = 2
                spread_virus(nx, ny, copyed)


def set_three_walls(start, depth):
    global max_val

    if depth == 3:
        copyed = copy.deepcopy(arr)

        length = len(virus_list)
        for i in range(length):
            [virus_x, virus_y] = virus_list[i]
            spread_virus(virus_x, virus_y, copyed)

        max_val = max(max_val, get_safe_area(copyed))
        return

    for i in range(start, n * m):
        x = int(i / m)
        y = int(i % m)

        if arr[x][y] == 0:
            arr[x][y] = 1
            set_three_walls(i + 1, depth + 1)
            arr[x][y] = 0


if __name__ == '__main__':
    # 사용자로부터 가로세로입력받기
    n, m = input().split(' ')  # n은 세로, m은 가로
    n, m = int(n), int(m)

    # n,m 크기조건을 만족하면, 사용자로부터 입력받음.
    if 3 <= n and m <= 8:
        for i in range(n):
            arr.append([int(x) for x in input().split()])   # 사용자로부터 NxM에 해당하는 리스트 받기.

        # print(arr)
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 2:
                    virus_list.append([i, j])   # 바이러스가 어디있는지 좌표 저장.

        set_three_walls(0, 0)   # 벽 3개 치기...
        print(max_val)          # 결과값 출력

    else:
        exit()