14502-연구소

www.acmicpc.net/problem/14502

1. 벽 세개를 세우는 모든 경우의 수를 순열로 구현

2. 각 경우마다 DFS 로 전염을 시켜준다.

3. 전염 후 안전한 구역이 몇 곳인지 구하여 더 큰 값으로 업데이트 한다.

from itertools import combinations

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

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

n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

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

# 벽을 설치하는 모든 경우의 수들 cases
loc_info = []
for y in range(n):
    for x in range(m):
        if not arr[y][x]:
            loc_info.append((y,x))
cases = list(combinations(loc_info,3))

# 초기 바이러스가 위치한 위치들 virus_locs
virus_locs = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            virus_locs.append((i,j))

answer = 0
for case in cases:
    # 벽설치
    temp = [arr[i][:] for i in range(len(arr))]
    for v in case:
        temp[v[0]][v[1]] = 1

    # 바이러스 위치에서 dfs 시작
    for virus_loc in virus_locs:
        dfs(virus_loc[0],virus_loc[1])

    # 전염된 연구소에 안전구역 몇개인지 카운트
    cnt = 0
    for i in range(n):
        for j in range(m):
            if not temp[i][j]:
                cnt += 1
    answer = max(cnt,answer)

print(answer)