[백준] 15683번 감시 (Python)

백준 15683 감시

문제를 읽으며 BFS 탐색 혹은 DFS 탐색을 활용해야 한다고 생각했다. grid에 업데이트 하기엔 DFS 탐색이 유리하다는 생각에 DFS 탐색을 활용해서 풀어야겠다고 생각했다. N-Queen 문제를 고려하면 DFS가 grid rollback엔 유리하다는 것을 알 수 있다. DFS 뿐만 아니라, 조사해야 하는 요소(CCTV)에 대해서 저장할 리스트가 필요했다. 5번 CCTV (4방향이기 때문)를 제외한 리스트를 candidate로 저장하며, 5번 CCTV를 제외한 CCTV에 대해서 조사하기 위해서 candidate 리스트를 선언하고 0요소를 가진 인덱스의 갯수를 센 후, 해당 개수에서 CCTV가 "새로" 감시하게 된 요소의 개수를 세도록 했다. 로직은 이러하다.

1. 0 의 인덱스 즉, 무엇으로부터도 감시받지 않는 영역의 개수를 센다.
2. 카메라의 위치, 벽을 포함한 위치를 빼고 계산하도록 한다.
3. 카메라가 감시하는 영역은 grid_count를 1씩 증가 시킨다. 롤백하는 경우를 위해서 grid_count를 활용해야 한다.
4. 런타임을 줄이기 위해서 5번 카메라는 grid에 미리 업데이트 하고, 나머지는 candidate 리스트에 넣는다.
5. DFS 탐색을 활용해 candidate에 있는 모든 CCTV를 탐색하고, 카메라의 고개를 돌릴 때마다 rollback 해준다.

import sys

def update_grid(y, x, dy, dx):
    tmpY = y + dy
    tmpX = x + dx
    cnt = 0
    while n > tmpY >= 0 and m > tmpX >= 0 and grid[tmpY][tmpX] != 6:
        if grid_cnt[tmpY][tmpX] == 0 : cnt += 1
        grid_cnt[tmpY][tmpX] += 1
        tmpY += dy
        tmpX += dx
    return cnt

def rollback(y, x, dy, dx):
    tmpY = y + dy
    tmpX = x + dx
    while n > tmpY >= 0 and m > tmpX >= 0 and grid[tmpY][tmpX] != 6:
        grid_cnt[tmpY][tmpX] -= 1
        tmpY += dy
        tmpX += dx

def DFS(idx, cnt):
    if cnt == 0:
        print(0)
        exit(0)
    if idx == len(candidates):
        return cnt
    y, x, c_num = candidates[idx]

    minV = 100
    for d in range(turn_avil[c_num]):
        tmpC = 0
        for tmpDy, tmpDx in cctv[c_num]:
            dy, dx = tmpDy, tmpDx
            for _ in range(d):
                dy = - tmpDx
                dx = tmpDy
                tmpDy = dy
                tmpDx = dx
            tmpC += update_grid(y, x, dy, dx)
        minV = min(minV, DFS(idx + 1, cnt - tmpC))
        for tmpDy, tmpDx in cctv[c_num]:
            dy, dx = tmpDy, tmpDx
            for _ in range(d):
                dy = - tmpDx
                dx = tmpDy
                tmpDy = dy
                tmpDx = dx
            rollback(y, x, dy, dx)
    return minV


inp = sys.stdin.readline
n, m = map(int, inp().split())
grid = [list(map(int, inp().split())) for _ in range(n)]
grid_cnt = [[0 for _ in range(m)] for _ in range(n)]
turn_avil = [0, 4, 2, 4, 4]
candidates = []
cctv_5 = []
tmpC = 0
cctv = [
    [],
    [[0, 1]],
    [[0, -1], [0, 1]],
    [[1, 0], [0, 1]],
    [[0, -1], [1, 0], [0, 1]]
]

for y in range(n):
    for x in range(m):
        if grid[y][x] == 0:
            tmpC += 1
        else:
            grid_cnt[y][x] += 1
            if 5 > grid[y][x] > 0:  
                candidates.append([y, x, grid[y][x]])
            if grid[y][x] == 5:
                cctv_5.append([y, x])

for y, x in cctv_5:
    tmpC -= update_grid(y, x, 0, 1)
    tmpC -= update_grid(y, x, 1, 0)
    tmpC -= update_grid(y, x, 0, -1)
    tmpC -= update_grid(y, x, -1, 0)

print(DFS(0, tmpC))