문제: https://www.acmicpc.net/problem/14502

풀이

완전탐색과 dfs로 해결했다.
지도에서 0에 해당하는 인덱스를 리스트에 넣어두고, 이 리스트에서 3개 조합을 만들었다.
조합으로 뽑은 세 개의 인덱스를 1로 만든 후 이때 바이러스가 얼마나 퍼지는지를 dfs로 계산했다.
그 후 안전영역 후보를 리스트에 넣어둔다.
이 작업을 모든 조합에 실시하고 이 중 가장 큰 안전영역 값을 출력한다.

소스코드

from itertools import combinations
import sys
input = sys.stdin.readline

def spreadable(next_x, next_y, n, m, VISITED):
    return 0 <= next_x < n and 0 <= next_y < m and new_map[next_x][next_y] == 0 and VISITED[next_x][next_y] == True


def dfs(n, m, new_map, VISITED):
    stack = []
    stack.append((i, j))

    while stack:
        x, y = stack.pop()
        VISITED[x][y] = False

        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = x + dx, y + dy
            if spreadable(next_x, next_y, n, m, VISITED):
                new_map[next_x][next_y] = 2
                stack.append((next_x, next_y))


if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    maps = [list(map(int, input().strip().split())) for _ in range(n)]
    blanks = []
    safe_section = []

    for i in range(n):
        for j in range(m):
            if maps[i][j] == 0:
                blanks.append((i, j))

    blank_combi = list(combinations(blanks, 3))

    for combi in blank_combi:
        new_map = list(map(list, maps))
        VISITED = [[True] * m for _ in range(n)]

        for x, y in combi:
            new_map[x][y] = 1

        for i in range(n):
            for j in range(m):
                if new_map[i][j] == 2 and VISITED[i][j] == True:
                    dfs(n, m, new_map, VISITED)

        zero_cnt = 0
        for row in new_map:
            zero_cnt += row.count(0)

        safe_section.append(zero_cnt)

    print(max(safe_section))