dfs, copy

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

1. 5번 CCTV까지 감시 할 수 있는 방향을 모두 리스트에 표시
2. CCTV 목록을 통해 완전 탐색
3. 맨 처음 카메라가 감시 할 수 있는 방향을 모두 방문 표시하고, depth를 늘려가면서 CCTV 리스트를 순차탐색한다. 즉 다음 CCTV가 감시 할 수 있는 부분도 처리해준다. 그리고 각 방향을 탐색할때마다 복원해주면서 가장 작은 값 찾으면 된다.

각 방향을 돌면서 > dfs (다른 카메라까지 전부 탐색)

import copy
n, m = map(int, input().split())
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))
cctv = []
# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(n):
	for j in range(m):
		if 0 < graph[i][j] < 6:
			cctv.append([graph[i][j], i, j])

# cctv가 이동할 수 있는 방향 
mode = [[],
       [[0], [1], [2], [3]],
       [[0, 2], [1, 3]],
       [[0, 1], [1, 2], [2, 3], [3, 0]],
       [[0, 1, 2], [1, 2, 3],[2, 3, 0], [3, 0, 1]],
       [[0, 1, 2, 3]]
       ]

def dfs(depth, graph):
	global min_result
	if depth == len(cctv):
		count = 0
		for i in range(n):
			count += graph[i].count(0)
		min_result = min(min_result, count)
		return
	temp = copy.deepcopy(graph)
	cctv_dir, x, y = cctv[depth]
	for each_dir in mode[cctv_dir]:
		# 감시 할 수 있는 방향 모두 표시 
		fill(temp, x, y, each_dir)
		# 다음 카메라 방향 
		dfs(depth + 1, temp)
		# 다시 복원 
		temp = copy.deepcopy(graph)



def fill(graph, x, y, mn):
	for i in mn:
		nx = x
		ny = y
		# 끝까지 이동 벽 만나거나 범위 벗어나면 종료 , 방문 표시해주기 
		while True:
			nx += dx[i]
			ny += dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				break
			if graph[nx][ny] == 6:
				break
			if graph[nx][ny] == 0:
				graph[nx][ny] = 7
min_result = int(1e9)
dfs(0, graph)
print(min_result)