백준 - 15683 : 감시 (G4)

 1import copy, sys
 2
 3N, M = map(int, input().split())
 4L = [list(map(int, input().split())) for _ in range(N)]
 5cctv = []
 6direction = [[[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]],
 7[[(-1, 0), (1, 0)], [(0, -1), (0, 1)]],
 8[[(-1, 0), (0, -1)], [(0, -1), (1, 0)], [(1, 0), (0, 1)], [(0, 1), (-1, 0)]],
 9[[(-1, 0), (0, -1), (1, 0)], [(0, -1), (1, 0), (0, 1)], [(1, 0), (0, 1), (-1, 0)], [(0, 1), (-1, 0), (0, -1)]],
10[[(-1, 0), (0, -1), (1, 0), (0, 1)]]]
11res = sys.maxsize
12
13for i in range(N):
14    for j in range(M):
15        if 1 <= L[i][j] <= 5:
16            cctv.append((L[i][j]-1, i, j))
17
18def dfs(map_, depth):
19    global res
20
21    if depth == len(cctv):
22        cnt = 0
23        for i in range(N):
24            for j in range(M):
25                if map_[i][j] == 0: cnt += 1
26        res = min(cnt, res)
27        return
28    ctype, cx, cy = cctv[depth]
29    for i in direction[ctype]:
30        new_map = copy.deepcopy(map_)
31        for j in i:
32            nx, ny = cx, cy
33            while True:
34                nx += j[0]
35                ny += j[1]
36
37                if not 0 <= nx < N or not 0 <= ny < M or map_[nx][ny] == 6:
38                    break
39                new_map[nx][ny] = 7
40        dfs(new_map, depth+1)
41
42dfs(L, 0)
43print (res)