문제

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

나의 코드

"""

"""

import copy
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
pan = [ list(map(int, input().split())) for _ in range(n) ]
cctv = []
cctv_dir = [
            [],
            [[0], [1], [2], [3]],
            [[0, 2], [1, 3]],
            [[0, 1], [1, 2], [2, 3], [0, 3]],
            [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
            [[0, 1, 2, 3]]
] # cctv의 회전 방향을 기록, 1번 cctv는 4방향이라 0, 1, 2, 3, 2번 cctv는 북남 또는 동서이기 때문에 [0, 2], [1, 3]으로 기록

for i in range(n): # cctv번호와 좌표를 찾는 반복문
    for j in range(m):
        if 1 <= pan[i][j] <= 5:
            cctv.append((pan[i][j], i, j))

def blind_spot(pan): # 사각지대 개수를 찾는 함수

    blind_cnt = 0
    for i in range(n):
        for j in range(m):
            if pan[i][j] == 0:
                blind_cnt += 1
    return blind_cnt

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 북, 동, 남, 서
def watch(board, dir, x, y):

    for k in dir:
        mx = x
        my = y
        while True:
            mx += dx[k]
            my += dy[k]
            if not (0 <= mx < n and 0 <= my < m): # 범위를 벗어나거나 벽을 만나는 경우 break
                break
            if board[mx][my] == 6:
                break
            elif board[mx][my] == 0: # cctv 범위내에 있으면 감시 영역은 7로 기록
                board[mx][my] = 7

def dfs(depth, pan):
    global answer

    if depth == len(cctv): # cctv의 개수만큼 dfs가 돌았으면 사각지대의 개수를 찾은 후 최소값 갱신 후 return한다.
        answer = min(answer, blind_spot(pan))
        return

    # cctv 감시가 계속 업데이트 되므로 계속 복사해주어서 갱신한다.
    tmp = copy.deepcopy(pan)
    cctv_num, x, y = cctv[depth]
    for i in cctv_dir[cctv_num]: # cctv 번호에 따른 회전 방향을 기록해놓은 리스트에서 꺼낸다.
        watch(tmp, i, x, y)
        dfs(depth+1, tmp)
        tmp = copy.deepcopy(pan) # 백트래킹 처럼 원 상태로 돌려 놓는다.

answer = 1e9
dfs(0, pan)
print(answer)
    

설명

백트래킹을 이용해 모든 경우의 수에 대해 탐색할줄 알아야 한다.

또한 cctv_dir, cctv 번호마다 회전방향을 기록해놓은 리스트를 만들 생각을 해야했는데 못했었다.

참고 자료