백준 15683번 - 감시 [Python]

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

15683번: 감시

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

→	←	↑	↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

문제 유형 / 난이도

완전 탐색 / 골드 4

문제 풀이

우선 모든 cctv에 대해서 발생할 수 있는 모든 경우의 수를 알아봐야하기 완전 탐색이다.

모든 cctv의 1차적인 경우의 그래프를 구하고 1개의 cctv를 회전시킨 후의 그래프를 구하고 또 회전시키고 그래프를 구하고 ... 여기서 부분 문제를 뽑을 수 있다.

 

1. 부분 문제

cctv 1개가 감시할 수 있는 범위를 "#"로 표시한다.

 

2. base case

모든 cctv에 대해서 알아봤을 때 해당 그래프의 사각지대를 구하고 최솟값을 갱신한다.

 

3. cctv에 따른 감시 구현

각각의 cctv를 회전시켜보면 중복되는 모양이 발생한다는 점을 알 수 있다. 따라서 먼저 cctv의 종류에 대해서 구분하고 각각의 cctv가 회전했을 때 나올 수 있는 경우를 미리 구해놓으면 중복을 제거할 수 있다.

 

4. 2차원 그래프 copy

완전 탐색, 백트래킹, dfs 같이 재귀를 활용하는 구조는 트리를 생각해야한다. 이 2차원 그래프를 왜 copy 해야하는지를 코드 레벨에서만 보면 잘 보이지 않지만 트리의 형태로 가져와서 생각하면 쉽게 보인다.

4개의 cctv가 있다고 할 때 1 -> 2 -> 4 -> 6 까지 cctv를 회전해서 base case에 도달한 후 7번으로 for문을 통해 넘어갈 때 어떤 그래프를 가지고 cctv를 회전 시켜야할까? 바로 dfs(2)의 4번 그래프를 대상으로 결과를 구한다. 왜냐하면 6번에서 이미 "#"으로 감시영역을 표시했기 때문에 표시되지 않은 그래프가 필요하다. 따라서 dfs(1)의 원본 그래프인 copyGraph로 갱신해야한다. 또한 그래프의 변화가 있고 이전 dfs의 그래프를 사용해야한다면 dfs마다 복사본을 만들어사용해야한다. 이유는 간단하다. 원본 graph에 손대면 이전 그래프를 알 수 없다.

Python

import sys
from copy import deepcopy
input = sys.stdin.readline


def findSpot(graph):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                cnt += 1
    return cnt

def fill(graph, rotate, x, y):
    for d in rotate:
        nx, ny = x, y
        while True:
            nx += dx[d]
            ny += dy[d]
            if nx < 0 or nx >= n or ny < 0 or ny >= m: break
            if graph[nx][ny] == 6: break
            graph[nx][ny] = '#'

def bf(graph, depth):
    global ans

    if depth == len(cctv):
        cnt = findSpot(graph)
        if ans > cnt:
            ans = cnt
        return
    
    copyGraph = deepcopy(graph)
    cctvType, x, y = cctv[depth]
    
    for rotate in mode[cctvType]:
        fill(copyGraph, rotate, x, y)
        bf(copyGraph, depth+1)
        copyGraph = deepcopy(graph)

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

graph = []
cctv = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(m):
        if graph[i][j] != 0 and graph[i][j] != 6:
            cctv.append((graph[i][j], i, j))
            
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]]
]

#     북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

ans = int(1e9)
bf(graph, 0)
print(ans)

feedback

맨 처음에 1개 방향의 감시를 구현하고 5개의 상황에 맞춰 회전 시킴으로써 구현했더니 시간초과와 메모리초과가 동시에 발생했다. 따라서 최적화가 필요했는데 최적화하는 방법이 생각이 나지않아 해당 부분을 참고했다.

 

📝 메모: 중복되는 모양 제거하고 한쪽 끝에서 반대쪽 끝까지 move 구현