문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
n, m의 범위가 작은걸 보고 완전탐색을 이용해서 풀어야 하나 생각 했어야 했다.
모든 경우에 벽은 다 일일이 세어보고 바이러스를 유포시킨 다음 안전지대의 개수를 세야 한다.


2. 시간복잡도
O(NM^4)인가?
일단 BFS 부분은 알려져 있듯이 O(NM)이고 벽을 3개 세우는 부분은
모든 부분에 대해 탐색해야 하므로 O(NM^3)이라고 생각한다. 그리고 완전탐색을
돌리는 와중에 BFS가 호출되므로 결국 O(NM^4)가 되고 N과 M은 각각 8이 최대니깐
(8 * 8)^4 = 2^24 = 16,777,216 충분한데? 
"""

from collections import deque
from sys import stdin
import copy
input = stdin.readline

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

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

def bfs():
    global answer
    q = deque()
    map2 = copy.deepcopy(map) # 2차원 배열을 복사하는 부분

    """ 바이러스가 있는 지점에서 시작한다. 
    동시에 유포해야 하니깐 이렇게 미리 바이러스 지점을 큐에 집어넣는다."""
    for i in range(n): 
        for j in range(m):
            if map2[i][j] == 2:
                q.append((i, j))

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < m:
                if map2[mx][my] == 0:
                    map2[mx][my] = 2
                    q.append((mx, my))

    global answer
    cnt = 0
    for i in range(n):
        cnt += map2[i].count(0)

    answer = max(answer, cnt)

def wall(cnt): # 백트래킹 부분. 벽이 3개 다 세워지면 bfs를 탐색한다.
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if map[i][j] == 0:
                map[i][j] = 1
                wall(cnt+1)
                map[i][j] = 0

wall(0)
print(answer)
    

느낀점

• 백트래킹을 이용해서 모든 경우의 벽을 세우는 부분
• copy를 import해서 bfs 탐색할때 마다 임시 2차원 배열을 생성하는 부분

위의 2가지 부분을 확실히 알고가야할 문제이다