[15683] 감시

문제

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

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

풀이

cctv가 감시하는 방향의 최대 경우의 수는 4개 입니다. 3, 4번 cctv의 경우 4가지의 방향을 만들 수 있기 때문입니다.

cctv의 최대 개수는 8이기 때문에 감시할 수 있는 영역의 총 경우의 수는 4 ^ 8 = 65,536라 할 수 있습니다. 많이 않은 수이기 때문에 모든 경우의 수를 구해주는 방식으로 풀었습니다.

배열 dirs[i]는 i+1 번째 카메라의 방향을 의미합니다. 해당 배열을 이용해서 감시되는 영역들에 표시를 할 수 있게 했습니다.

import sys

N, M = map(int, sys.stdin.readline().split())
result = sys.maxsize
board, cctv = [], []
dirs = [
    [[(1, 0)], [(-1, 0)], [(0, 1)], [(0, -1)]],
    [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]],
    [[(-1, 0), (0, 1)], [(0, 1), (1, 0)], [(1, 0), (0, -1)], [(-1, 0), (0, -1)]],
    [[(-1, 0), (0, 1), (1, 0)], [(0, 1), (1, 0), (0, -1)], [(1, 0), (0, -1), (-1, 0)], [(0, -1), (-1, 0), (0, 1)]],
    [[(-1, 0), (0, 1), (1, 0), (0, -1)]]
]

for i in range(N):
    row = map(int, sys.stdin.readline().strip().split())
    board.append([])
    for j, c in enumerate(row):
        board[-1].append(c)
        if c != 0 and c < 6:
            cctv.append((i, j, c - 1))

def can_watch(r, c):
    if not 0 <= r < N or not 0 <= c < M:
        return False
    if board[r][c] == 6:
        return False
    return True

def painting(cur_r, cur_c, direction, color):
    for move_r, move_c in direction:
        for i in range(1, max(N, M)):
            r, c = cur_r + (move_r * i), cur_c + (move_c * i)
            if not can_watch(r, c):
                break
            board[r][c] += color

def find(depth):
    global result
    if depth == len(cctv):
        count = 0
        for r in range(N):
            count += board[r].count(0)
        result = min(result, count)
        return
    r, c, current_cctv = cctv[depth]
    for direction in dirs[current_cctv]:
        painting(r, c, direction, 7)
        find(depth + 1)
        painting(r, c, direction, -7)

find(0)
print(result)