백준 15683 감시 (Python)

문제 링크는 여기!

15683번: 감시

 

심심치 않게 나오는 CCTV 문제 중 하나이다! 

사각지대가 최소로 나오는 경우로 카메라 방향을 맞춰야 하고, 그 때의 사각지대 개수를 출력하는 문제!

 

 

항상 탐색문제를 풀때마다 생각하는 건데, 우리 모두 탐색문제라는 건 알지만 탐색을 할 최적의 방법을 찾는 것이 큰 문제인 것 같아요. 어떤 것을 dfs의 재귀 조건으로 잡을 것인지, 탐색을 할 때에 새로운 리스트를 써줄 것인지 등등!

저는 백트래킹을 쓰려고 생각하지 않았기 때문에(예외조건이 있다면 댓글 남겨주시면 감사하겠습니다.) 카메라 하나의 방향을 정해줄 때마다 사각지대를 없애가는 방법 vs 카메라의 방향을 다 정하고 한번에 사각지대를 없애는 방법 

중 고민을 한 결과 방향을 다 정하고 한번에 사각지대를 없애기로 했습니다.

 

카메라의 종류에 따라 방향의 경우의 수를 미리 딕셔너리화 해서 이 중 하나를 선택하는 방향으로 dfs를 진행했습니다. 

 

 

 

 

코드

#백준 15683 감시
#code created by jungwonkkim

delta = [(0,1),(0,-1),(1,0),(-1,0)]
direction = {1:[[0],[1],[2],[3]], 2:[[0,1], [2,3]], 3: [[0,2],[1,3],[0,3],[1,2]], 4: [[0,1,2], [1,2,3],[2,3,0],[3,0,1]], 5:[[0,1,2,3]]}

def dfs(n, arr):
    global min_sq
    if n == len(camera):
        visited = [[False for _ in range(M)] for _ in range(N)]
        for idx, c in enumerate(camera):
            x = c[0]
            y = c[1]
            for element in arr[idx]:
                c = 1
                while True:
                    nx = x + delta[element][0]*c
                    ny = y + delta[element][1]*c
                    if 0<=nx<N and 0<=ny<M and office[nx][ny] !=6:
                        if office[nx][ny]==0 and visited[nx][ny] == False:
                            visited[nx][ny] = True
                        c+=1
                    else:
                        break
        cnt = 0
        for ii in range(N):
            for jj in range(M):
                if office[ii][jj] == 0 and visited[ii][jj] == False:
                    cnt +=1
        if min_sq > cnt:
            min_sq = cnt
        return
    for ele in direction[office[camera[n][0]][camera[n][1]]]:
        arr.append(ele)
        dfs(n+1, arr)
        arr.pop()


N, M = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(N)]
camera = []
min_sq = 0
for i in range(N):
    for j in range(M):
        if 1<=office[i][j]<=5:
            camera.append((i,j))
        if office[i][j] == 0:
            min_sq +=1
dfs(0,[])
print(min_sq)