[백준] 15683 감시

---

사무실에 설치된 CCTV는 위 다섯가지 중 하나이다. CCTV가 감시할 수 있는 방향은 위와 같고  90도 회전이 가능하다. 이때 최소 사각지대의 크기를 구하는 문제이다. N의 최대 크기가 8이기 때문에 백트래킹, 브루트 포스 알고리즘을 통해 해결할 수 있다.

 

1. 각 CCTV가 감시할 수 있는 방향을 구한다.

예를 들어, 1번은 상, 하, 좌, 우 각 한 방향씩 감시 가능하다. 2번 CCTV는 상하, 좌우 두 방향 감시가 가능하다.

 

2. CCTV를 모두 설치할 경우 사각지대의 크기를 구한다.

 

from sys import stdin
readline = stdin.readline

def main():
    cctvs = []
    _map = []
    for i in range(N):
        row = list(map(int, readline().split()))
        _map.append(row)
        for j in range(M):
            if 0 < row[j] < 6:
                cctvs.append([i, j, row[j]])

    dfs(_map, 0, cctvs)

def dfs(_map, cnt, cctvs):
    global ans, dirs
    temp = [[_map[i][j] for j in range(M)] for i in range(N)]
    if cnt == len(cctvs): # CCTV를 모두 설치한 경우
        num = 0
        for i in range(N):
            num += temp[i].count(0)
        ans = min(ans, num)
        return
    
    r, c, cctv = cctvs[cnt]
    for i in dirs[cctv]:
        watch(temp, r, c, i) # 해당 방향으로 감시 확장
        dfs(temp, cnt + 1, cctvs)
        temp = [[_map[i][j] for j in range(M)] for i in range(N)] # 초기화

def watch(_map, r, c, _dir):
    for d in _dir: # 주어진 방향에 대해
        nr, nc = r, c # 확장
        while 0 <= nr < N and 0 <= nc < M:
            if _map[nr][nc] == 6: break
            if _map[nr][nc] == 0:
                _map[nr][nc] = -1
            
            nr += dr[d]
            nc += dc[d]

if __name__ == '__main__':
    N, M = map(int, readline().split())
    ans = N * M
    dr, dc = (1, -1, 0, 0), (0, 0, 1, -1)
    dirs = [[], [[0], [1], [2], [3]], [[0, 1], [2, 3]], [[0, 2], [2, 1], [1, 3], [3, 0]], 
            [[0, 2, 3], [0, 1, 2], [1, 2, 3], [0, 1, 3]], [[0, 1, 2, 3]]]
    main()
    print(ans)