15683: 감시

• dx, dy, cctv_modes 이 세개의 list를 통해 모든 cctv와 각 cctv 별 방향으로 탐색을 진행함
• dfs 순회를 진행하면서 backtracking을 해줘야하는데, 이때 1) dfs의 input parameter로 Room을 넣어주고, 2) deepcopy를 이용해 각 depth의 room 상태를 백업 및 복구해줌

import sys
import copy

# 상 우 하 좌 순서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
cctv_modes = [[],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]]] #dx, dy에서의 index를 저장함

def dfs(depth, Room):
    global min_result
    if depth == len(cctv):
        local_min_result = 0
        for i in range(N):
            for j in range(M):
                if Room[i][j] == 0:
                    local_min_result += 1
        min_result = min(min_result, local_min_result)
        return
    room = copy.deepcopy(Room) #독립적인 새로운 객체 생성
    cctv_type, x, y = cctv[depth]
    for cctv_mode in cctv_modes[cctv_type]: #cctv별로 모든 방향을 순회하며 backtracking 진행
        for idx in cctv_mode:
            nx = x; ny = y
            while True:
                nx += dx[idx]; ny += dy[idx]
                if nx < 0 or ny < 0 or nx >= N or ny >= M or room[nx][ny] == 6:
                    break
                elif room[nx][ny] == 0:
                    room[nx][ny] = -1
        dfs(depth+1, room)
        room = copy.deepcopy(Room) #backtracking을 위해 room 해당 단계 전까지 복구

N, M = map(int, sys.stdin.readline()[:-1].split())
Room = []; cctv = []
for i in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    Room.append(tmp)
    for j in range(M):
        if tmp[j] in [1, 2, 3, 4, 5]:
            cctv.append([tmp[j], i, j])

min_result = int(1e9)
dfs(0, Room)
print(min_result)