[백준] 감시 복기

1. 문제

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

2. 아이디어

DFS
1) cctv 위치와 갯수 세주기
2) 각 cctv가 감시할 수 있는 위치 검사

3. 시간 복잡도

cctv의 갯수 (곱하기) 감시할 수 있는 방향의 갯수 (곱하기) 위치 검사
8 (곱하기) 4 (곱하기) (N+M)

4. 코드

N, M = map(int, input().split())

graph = []
cctv = []
wall = 0

for i in range(N):
    lists = list(map(int, input().split()))
    graph.append(lists)
    for j in range(len(lists)):
        if graph[i][j] != 0 and graph[i][j] !=6 :
            cctv.append((i,j))
        if graph[i][j] == 6:
            wall += 1


dxy = [[0,1],[-1,0],[0,-1],[1,0]]

move = dict()
move[1] = [[0],[1],[2],[3]]
move[2] = [[0,2],[1,3]]
move[3] = [[0,1],[1,2],[2,3],[3,0]]
move[4] = [[0,1,2],[1,2,3],[2,3,0],[3,0,1]]
move[5] = [[0,1,2,3]]

res = float("-Inf")


def dfs(L, n):
    global res
    if L == len(cctv):
        res = max(res, n)
        return

    x, y = cctv[L][0], cctv[L][1]

    for dir in move[graph[x][y]]: # [(0,1,2),(1,2,3),(2,3,0),(3,0,1)]
        visited = []
        
        for dd in dir: # dd = (0,1,2)
            nx, ny = x, y
            while True:
                nx, ny = nx+dxy[dd][0], ny +dxy[dd][1]
                if  0 > nx or 0> ny or nx >= N or ny >=M:
                    break
                if graph[nx][ny] == 6:
                    break
                
                if graph[nx][ny] == "#" or graph[nx][ny] != 0:
                    continue

                visited.append([nx,ny])
                graph[nx][ny] = "#"
                

        dfs(L+1,n + len(visited)) 

        for a,b in visited:
            graph[a][b] = 0


dfs(0,0)
print(N*M - len(cctv)- res-wall)

5. 오답노트

1. [문제 제대로 읽지 않음 ] 최대 감시 구역 갯수를 찾는 것이 아닌, 최소 사각지대를 찾는 것이다.
2. [구현에서 제대로 못함] cctv의 갯수를 빼주지 않음 , 벽의 갯수 빼주지 않음
3. [기준을 제대로 세우지 못함] cctv의 감시 가능 검사를 할 때 if 문에 대한 구체적 기준을 세우지 않았음
4. [구현에서 제대로 못함] nx,ny의 좌표는 계속 바뀌지만, 방향을 바뀔 때는 초기 x,y값을 다시 부여해야 한다.
5. [중복을 빼주지 못함] 방문 갯수를 세어줄 때, 중복으로 셌다.