완전탐색 - 연구소

itertools 안쓰고 조합 구하는 방법으로 다시 풀어보기
중요 포인트: 빈 공간(0)의 좌표를 모두 저장해서 3개씩 조합할 수 있는 가능한 모든 조합을 탐색해야 함

from itertools import combinations

n, m = list(map(int, input().split()))
maps = []
empty_list = []
virus_list = []
max_cnt = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


# -----바이러스 퍼뜨리는 함수
def spread_virus(x, y):

    for i in range(0, 4):
        # 상하좌우 좌표
        nx = dx[i] + x  # x가 아닌 nx임을 주의!
        ny = dy[i] + y
        # 상하좌우 중 맵 내부이면서 빈 공간이면 바이러스 퍼짐
        if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
            maps[nx][ny] = 4  # 바이러스 퍼진 곳: 4
            spread_virus(nx, ny)


# -----

for i in range(0, n):
    line = list(map(int, input().split()))
    for j in range(0, len(line)):
        # 빈 공간이면
        if line[j] == 0:
            # 빈공간 리스트에 좌표 저장
            empty_list.append([i, j])
        # 바이러스면
        elif line[j] == 2:
            # 바이러스 리스트에 좌표 저장
            virus_list.append([i, j])
    maps.append(line)

# 빈 공간들 중에 벽 3개를 세우는 가능한 모든 조합 구하기
all_comb = list(combinations(empty_list, 3))

for i in range(0, len(all_comb)):
    comb = list(all_comb[i])  # 각 경우의 벽을 세울 좌표 3개가 저장된 리스트
    cnt = 0  # 각 경우의 안전 영역 개수

    for j in range(3):
        x, y = comb[j]
        maps[x][y] = 3  # 새로운 벽(3) 3개 세우기

    # 바이러스 퍼뜨리기
    for k in range(0, len(virus_list)):
        x, y = virus_list[k]
        spread_virus(x, y)

    # 안전 영역 세기
    for line in maps:
        # 0이면 안전 영역
        cnt += line.count(0)

    # 안전 영역 최댓값 갱신
    if cnt > max_cnt:
        max_cnt = cnt

    # 이번 경우가 끝났으니 맵 원상복귀
    for j in range(0, len(maps)):
        for k in range(0, len(maps[j])):
            # 3 이거나 4 라면 (새롭게 새운 벽이거나 퍼진 바이러스 영역이었다면)
            if maps[j][k] == 3 or maps[j][k] == 4:
                maps[j][k] = 0  # 0으로 초기화

# 안전 영역 크기의 최댓값 출력
print(max_cnt)