[백준 15683번] 감시

import copy
n, m = map(int,input().split())

area = [list(map(int,input().split())) for _ in range(n)]

# 0은 빈 칸, 6은 벽, 1~5는 CCTV

def monitor_right(x,y,temp_area):
    total = 0
    for i in range(y+1,m):
        if temp_area[x][i] == 6:
            break
        elif temp_area[x][i] == 0:
            temp_area[x][i] = -1
            total += 1
    return total, temp_area

def monitor_left(x,y,temp_area):
    total = 0
    for i in range(y-1,-1,-1):
        if temp_area[x][i] == 6:
            break
        elif temp_area[x][i] == 0:
            temp_area[x][i] = -1
            total += 1
    return total, temp_area

def monitor_top(x,y,temp_area):
    total = 0
    for i in range(x-1,-1,-1):
        if temp_area[i][y] == 6:
            break
        elif temp_area[i][y] == 0:
            temp_area[i][y] = -1
            total += 1
    return total, temp_area

def monitor_down(x,y,temp_area):
    total = 0
    for i in range(x+1,n):
        if temp_area[i][y] == 6:
            break
        elif temp_area[i][y] == 0:
            temp_area[i][y] = -1
            total += 1
    return total, temp_area

def count_blind(result_area):
    total = 0
    for i in range(n):
        for j in range(m):
            if result_area[i][j] == 0:
                total += 1
    return total

cctv_cases= [
    [],
    [['right'],['down'],['left'],['top']],
    [['left','right'], ['top','down']],
    [['top','right'],['right','down'],['down','left'],['left','top']],
    [['left','top','right'],['top','right','down'],['right','down','left'],['down','left','top']],
    [['right','down','left','top']]
]

cctv_list = []

min_value = float("inf")

for i in range(n):
    for j in range(m):
        if area[i][j] != 0 and area[i][j] != 6:
            cctv_list.append((i,j,area[i][j]))

def monitor(start_x,start_y,area,cases):
    for case in cases:
        if case == 'left':
            monitor_left(start_x,start_y,area)
        elif case == 'right':
            monitor_right(start_x,start_y,area)
        elif case == 'top':
            monitor_top(start_x,start_y,area)
        elif case == 'down':
            monitor_down(start_x,start_y,area)

def dfs(depth,area):
    global min_value
    if depth == len(cctv_list):
        min_value = min(min_value,count_blind(area))
        return
    
    cctv_x, cctv_y, value = cctv_list[depth]
    temp_area = copy.deepcopy(area)
    
    for cases in cctv_cases[value]:
        monitor(cctv_x,cctv_y,temp_area,cases)
        dfs(depth+1,temp_area)
        temp_area = copy.deepcopy(area)

dfs(0,area)
print(min_value)

이번 문제는 1번부터 5번 CCTV가 감시하는 방향이 정해져있는데, 각각의 CCTV를 90도씩 회전할 수 있다는 가정하에 CCTV가 감시하지 않는 사각지대의 최소 크기를 구하는 문제이다.

 

이 문제는 구현하는데는 오래 걸리지 않았는데, 자꾸 몇몇 테스트케이스에서 실패하여 반례를 찾느라 시간을 많이 쏟았던 문제이다.

 

결국 내가 간과했던건 'CCTV로 감시하는 모든 경우의 수를 고려하지 않고 순서대로 감시 처리를 한 것'이다.

 

처음에 구현한 감시 처리 방식은 현재 좌표 기준에서 최대한 많이 감시할 수 있도록 하는 것이었는데, 그렇다보니 CCTV 감시 처리를 하는 순서에 따라 결과 값이 다르게 나오게 되고, 모든 경우의 수를 고려하지 않게 된다.(Greedy한 방식)

 

따라서 모든 경우의 수를 구하기 위해 순열을 사용하여 제출한 결과, 시간초과가 발생하게 되었다. 그 이유는 Stack 자료구조를 활용한 DFS를 사용하지 않고 순열로 경우의 수를 구하여 탐색하였기 때문이다.

 

많은 시간을 쏟아부은 덕분에 여러가지 배운 점이 있었다.

 

배운 점 및 느낀 점

1. 그래프에 값을 갱신할 때 갱신하는 순서가 결과에 영향을 줄 수 있는 문제는 '완전 탐색'으로 풀이하자.
2. 완전탐색을 할 때는 무조건 Stack 자료구조를 활용하는 DFS나 Queue 자료구조를 활용하는 BFS를 사용해야 시간복잡도를 최소화할 수 있다.(단순히 모든 경우의 수를 구할 경우 시간초과가 발생할 확률이 높다.)