연구소

풀이

 BFS DFS 모두 가능한 문제다. 나는 DFS로 풀었다. 이 문제의 핵심은 3개의 벽을 어떻게 세우느냐이다. 처음에는 벽을 세우는 기준에 대해 고민했지만, 이 문제에서는 벽 3개를 설치하는 모든 경우의 수를 고려해야 했다. 2차원 그래프에서 0인 값 3개의 좌표 조합을 구해야 했는데 나는 파이썬의 itertools 라이브러리의 combinatons 함수를 사용했다.

from itertools import combinations
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

# 2차원 그래프에서 0인 값 3개의 좌표 조합 구하기
temp = [ (x,y) for x in range(N) for y in range(M) if graph[x][y] == 0]
data = list(combinations(temp, 3))

# 동 서 남 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(graph, x, y, t):
    count = 1
    t[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < N and 0<= ny < M and graph[nx][ny] ==0 and t[nx][ny] == 0:
            count += dfs(graph, nx, ny, t)
    return count

result = 0
for i in data:
    t = [[0 for i in range(M)] for i in range(N)]
    count = 0
    safe = M*N

    # 벽 3개 세우기
    for j in range(3):
        x, y = i[j]
        graph[x][y] =1

    # 안전 구역 개수 구하기
    for j in range(N):
        for k in range(M):
            if graph[j][k] == 1:
                safe += -1
            if graph[j][k] == 2:
                count += dfs(graph, j,k,t)
    safe -= count

    # 안전 구역 최대값 구하기
    if safe > result:
        result = safe

    # graph 초기화
    for k in range(3):
        x, y = i[k]
        graph[x][y] = 0

print(result)

시간복잡도 : O(n*mC3) (N,M에 대해)