[백준 15683] 감시

문제 보기

이 문제는 브루트 포스 문제이다.

다음과 같은 감시카메라로 감시를 할 때, 주어진 맵에서 최소의 사각지대를 구해야한다.

감시카메라의 종류는 다음과 같다.

각 종류의 감시카메라가 90도마다 회전할 때의 최소 사각지대를 구해야한다.

다음 그림을 보면 이해할 수 있다.

위 그림을 설명하자면, CCTV 리스트에 있는 모든 카메라들에 대해서 4번씩 회전시키고, solution()함수를 재귀적으로 실행시킨다. 이때의 매개변수는 현재 CCTV 리스트와 그 index이다.

1. 리스트 내의 index가 0인 1번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 1번 CCTV를 4번 회전시킨다.)

2. 1번 CCTV의 각 회전에 대해서 리스트 내의 index가 1인 2번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 2번 CCTV를 4번 회전시킨다.)

...

이를 재귀적으로 표현한 부분으로, 모든 감시카메라가 4번씩 회전하는 모든 경우의 수는 111~114번째 줄에 구현되어 있다.

up, right, down, left 함수는 좌표가 주어졌을 때, 그 좌표로부터 상,하,좌,우로 감시하는 함수이다. (감시되는 영역은 2차원 배열에서 -1로 표시된다.)

47~100번째 줄은, DFS로 모든 경우의 수마다, 주어진 맵에서 사각지대를 구하는 부분이다.

import sys
from copy import deepcopy
 
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for c in range(n)]
 
 
def up(temp_board, r, c):
    count = 1
    for i in range(r, -1, -1):
        if temp_board[i][c] == 6:
            break
        temp_board[i][c] = -1
    return count
 
 
def right(temp_board, r, c):
    count = 1
    for j in range(c, m, 1):
        if temp_board[r][j] == 6:
            break
        temp_board[r][j] = -1
    return count
 
 
def down(temp_board, r, c):
    count = 1
    for i in range(r, n, 1):
        if temp_board[i][c] == 6:
            break
        temp_board[i][c] = -1
    return count
 
 
def left(temp_board, r, c):
    count = 1
    for j in range(c, -1, -1):
        if temp_board[r][j] == 6:
            break
        temp_board[r][j] = -1
    return count
 
 
def solution(idx, obs_list):
    global answer
    temp_board = deepcopy(board)
    if idx == list_size:
        # count all detection area
        for ((r, c), observer, offset) in obs_list:
            if observer == 1:
                if offset == 0:
                    right(temp_board, r, c)
                elif offset == 1:
                    down(temp_board, r, c)
                elif offset == 2:
                    left(temp_board, r, c)
                else:
                    up(temp_board, r, c)
            elif observer == 2:
                if offset == 0 or offset == 2:
                    right(temp_board, r, c)
                    left(temp_board, r, c)
                elif offset == 1 or offset == 3:
                    up(temp_board, r, c)
                    down(temp_board, r, c)
            elif observer == 3:
                if offset == 0:
                    up(temp_board, r, c)
                    right(temp_board, r, c)
                elif offset == 1:
                    right(temp_board, r, c)
                    down(temp_board, r, c)
                elif offset == 2:
                    down(temp_board, r, c)
                    left(temp_board, r, c)
                else:
                    left(temp_board, r, c)
                    up(temp_board, r, c)
            elif observer == 4:
                if offset == 0:
                    up(temp_board, r, c)
                    right(temp_board, r, c)
                    down(temp_board, r, c)
                elif offset == 1:
                    right(temp_board, r, c)
                    down(temp_board, r, c)
                    left(temp_board, r, c)
                elif offset == 2:
                    down(temp_board, r, c)
                    left(temp_board, r, c)
                    up(temp_board, r, c)
                else:
                    left(temp_board, r, c)
                    up(temp_board, r, c)
                    right(temp_board, r, c)
            else:
                up(temp_board, r, c)
                right(temp_board, r, c)
                left(temp_board, r, c)
                down(temp_board, r, c)
                
        # get the minimum space
        count = 0
        for r in range(n):
            for c in range(m):
                if temp_board[r][c] == 0:
                    count += 1
        answer = min(answer, count)
        return answer
 
    # traverse all occasion
    for i in range(4):
        obs_list[idx][2] = i
        solution(idx + 1, obs_list)
 
 
# make a list of observers
observer_list, list_size = list(), 0
for i in range(n):
    for j in range(m):
        if 0 < board[i][j] < 6:
            observer_list.append([(i, j), board[i][j], 0])
            list_size += 1
 
answer = sys.maxsize
solution(0, observer_list)
print(answer)