[BOJ] 감시 (G3, 15683)

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

 

골드 3 다운 쉽지  않은 문제.

처음 들었던 생각은 이거 어차피, 각 카메라가 비출 수 있는 최대 칸을 그리디하게 비추면 되는거 아닌가?

하지만, 몇 가지 문제가 있다.
(1) 동률일 경우 어떻게 처리?
(2) 동률일 경우 방향을 겹치게 비춰주면 그리디하다고 꼭 최대는 아님.. 안겹치게 비춰줘야 최대... 아 복잡..

즉, 그리디로는 풀기 어려우니 DFS 해 줘야 한다.

각 카메라별로 회전 방향이 정해져있는데, 두 개 이상의 경우는 두 개 이상의 방향이 합쳐졌다고 고려하면 된다.
1번 카메라는 상/하/좌/우
2번 카메라는 상하/좌우
3번 카메라는 상좌/상우/하좌/하우
4번 카메라는 상하좌/상하우/상좌우/하좌우
5번 카메라는 상하좌우

이 각각 중 1개씩 고르게 해서 불을 각 방향대로 비춰주고, 칸 수 세보고를 시도한다.
모든 카메라를 설치했을 때 칸수 세보고, 적은지 보고 돌려보고 브루트 포스 시킨다.

DFS + 브루트 포스 빡구현 문제. 그리디 아니다.

아, 주의 사항.
이차원 배열은 deepcopy를 해야 이전 상태를 별도로 분리하여 저장할 수 있다.
DFS할 때는 탐색을 하고 나오면 이전 상태로 원복해야 하는데, 구현이 쉽지가 않다.
deepcopy를 시켜, 이전 상태를 기억시키는 것이 중요하다.

import sys
import copy
input = sys.stdin.readline
# 칠하는 것은 # 이 아니라 int 통일을 위해 7번으로 진행한다.
# 보드를 돌리기가 어렵다. deepcopy를 써서 돌려줄 애를 기억해서 돌려야 한다!
def fill_camera(chosen_way, cx, cy, maps):
    for cur_way in chosen_way:
        mv = mv_list[cur_way]
        nx = cx
        ny = cy
        while True:
            nx += mv[0]
            ny += mv[1]
            if 0 <= nx < rows and 0 <= ny < cols:
                if maps[nx][ny] == 6:
                    break
                elif maps[nx][ny] == 0:
                    maps[nx][ny] = 7
            else:
                break
        
mv_list = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 위 아래 왼쪽 오른쪽
camera = [[], # 0번 없음
          [[0], [1], [2], [3]], # 1번이 선택 가능한 4방향,
          [[0, 1], [2, 3]], # 2번이 선택 가능한 2방향,
          [[0, 2], [0, 3], [1, 2], [1, 3]], # 3번이 선택 가능한 4방향
          [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], # 4번이 선택 가능한 4방향
          [[0, 1, 2, 3]]] # 5번이 선택 가능한 1방향

rows, cols = map(int, input().split())
cur_space = rows * cols

maps = []
camera_pos = [] # 이거의 깊이 만큼 dfs를 돌려줄 예정이다
for i in range(rows):
    cur_row = list(map(int, input().split()))
    maps.append(cur_row)
    for j in range(cols):
        if cur_row[j] in [1, 2, 3, 4, 5]:
            camera_pos.append([cur_row[j], i, j]) # 카메라 번호, 행, 열

def dfs(num_camera, maps):
    global min_space
    if num_camera == len(camera_pos):
        count = 0
        for i in range(rows):
            for j in range(cols):
                if maps[i][j] == 0:
                    count += 1
        if count < min_space:
            min_space = count
        return
        
    temp_map = copy.deepcopy(maps) 
    cur_tv, cur_x, cur_y = camera_pos[num_camera]
    for cur_mode in camera[cur_tv]:
        fill_camera(cur_mode, cur_x, cur_y, temp_map)
        dfs(num_camera + 1, temp_map)
        # 보드를 초기화해서 카메라 방향을 돌려야 하니까
        temp_map = copy.deepcopy(maps)

min_space = 1e18
dfs(0, maps)
print(min_space)