[BOJ] 백준 15683 감시 python

import copy
N,M = map(int,input().split())
mapp = []
check = [[0 for _ in range (0,M)] for _ in range (0,N)]
camera = []
dx,dy = [1,0,-1,0], [0,1,0,-1]
for i in range (0,N):
    a = list(map(int,input().split()))
    mapp.append(a)
    for j in range (0,M):
        if 1 <= a[j] <= 5:
            camera.append([a[j], i,j])
ans = int(1e9)
pattern = [[],[[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]]]
#pattern은 카메라 종류를 지시함
#카메라의 x,y는 위치
def view(area,mode,x,y):
    for i in mode:
        a,b = x,y
        while True:
            a += dx[i]
            b += dy[i]
            if 0 <= a < N and 0 <= b < M:
                if area[a][b] == 0:
                    area[a][b] = -1
                elif area[a][b] == 6:
                    break
            else:
                break
            
def dfs(depth, area):
    global ans
    if depth == len(camera):
        cnt = 0
        for i in range (0,N):
            cnt += area[i].count(0)
        ans = min(ans,cnt)
        area = copy.deepcopy(mapp)
        return
    
    new_area = copy.deepcopy(area)
    cctv,x,y = camera[depth]
    for i in pattern[cctv]:
        view(new_area,i,x,y)
        dfs(depth + 1, new_area)
        new_area = copy.deepcopy(area)
dfs(0,mapp)
print(ans)

 

삼성은 이런 카테고리의 문제를 많이 내는구나 싶었다.

백트래킹 / dfs를 잘 익힌 다음에 시험 보러 가는 것이 좋을 것 같다