[Gold III] 감시 - 15683

문제 링크

성능 요약

메모리: 33728 KB, 시간: 2208 ms

분류

구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹

문제 설명

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

1번	2번	3번	4번	5번

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번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 # 6 0
0 0 0 0 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 0 # 0 0 0
0 0 # 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 # 0 0 0

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

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

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

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

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

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

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의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력

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

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

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

출력

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

문제 풀이

문제 분석

이 문제는 사무실 내 CCTV들의 감시 방향을 적절히 설정하여 사각지대의 최소 크기를 구하는 문제입니다. 사무실은 N x M 크기의 격자 형태로 주어지며, 각 칸은 빈 칸(0), 벽(6), 또는 CCTV(1~5) 중 하나입니다. 각 CCTV는 종류에 따라 감시할 수 있는 방향의 조합이 다르고, 90도 단위로 회전할 수 있습니다. 목표는 모든 CCTV의 가능한 감시 방향 조합을 고려하여 사각지대(감시받지 못하는 빈 칸)의 최소 개수를 찾는 것입니다.

접근 방법

이 문제는 모든 CCTV의 가능한 감시 방향 조합을 시도해 보면서 사각지대 크기를 계산해야 합니다. 따라서 브루트포스 (완전 탐색) 알고리즘과 백트래킹 기법을 사용하여 해결합니다. 백트래킹을 사용하는 이유는, 각 CCTV의 방향을 결정할 때마다 전체 사무실 상태를 복사하여 다음 CCTV 방향 결정을 진행하고, 모든 CCTV의 방향이 결정되면 사각지대 크기를 계산한 후, 다시 이전 상태로 돌아가 다른 방향 조합을 시도해야 하기 때문입니다. 깊이 우선 탐색(DFS)을 사용하여 CCTV를 순서대로 처리하고, 각 CCTV마다 가능한 모든 방향 조합을 적용합니다.

구현 설명

구현은 다음과 같은 단계로 나눌 수 있습니다.

1. 입력 처리 및 CCTV 위치 저장

• 입력으로 주어진 사무실 정보를 2차원 배열 graph에 저장합니다.
• CCTV의 종류, 행 좌표, 열 좌표를 튜플 형태로 cctvs 리스트에 저장합니다. 이 리스트는 DFS에서 CCTV를 순서대로 처리하는 데 사용됩니다.

2. CCTV별 감시 방향 정의

• 각 CCTV 종류(1~5)마다 감시 가능한 방향 조합을 mode 딕셔너리에 정의합니다. 예를 들어, CCTV 1번은 4가지 방향(상, 우, 하, 좌) 중 하나를 감시할 수 있으므로 mode[1]은 [[0], [1], [2], [3]]으로 정의됩니다. 여기서 0, 1, 2, 3은 각각 상, 우, 하, 좌 방향을 나타냅니다.

3. 감시 영역 표시 함수 (detect) 구현

• detect(board, x, y, direction) 함수는 주어진 사무실 상태 (board), CCTV의 좌표 (x, y), 감시 방향 (direction)을 입력받아 해당 방향으로 감시되는 영역을 '#'으로 표시합니다.
  • 함수는 CCTV 위치에서 시작하여 해당 방향으로 계속 진행하며, 빈 칸(0)을 '#'으로 변경합니다.
  • 벽(6)을 만나거나 사무실 경계를 벗어나면 감시를 중단합니다.

4. 깊이 우선 탐색 (DFS)을 통한 완전 탐색

• DFS(cctv_idx, graph) 함수는 백트래킹을 이용하여 모든 CCTV의 방향 조합을 탐색합니다.
  • cctv_idx는 현재 처리 중인 CCTV의 인덱스를 나타냅니다.
  • 기저 조건: cctv_idx가 cctvs의 길이와 같아지면 모든 CCTV의 방향이 결정된 것이므로, 사각지대 크기를 계산하고 최소값(min_count)을 갱신합니다.
  • 각 CCTV마다 mode 딕셔너리에서 가능한 방향 조합을 가져와 순회합니다.
  • 각 방향 조합에 대해 board_copy = copy.deepcopy(graph)를 사용하여 현재 사무실 상태를 복사합니다. 복사본을 사용하는 이유는 백트래킹을 위해 각 방향 설정을 독립적으로 처리해야 하기 때문입니다.
  • 복사된 사무실 상태에서 선택된 방향 조합에 따라 detect 함수를 호출하여 감시 영역을 표시합니다.
  • 다음 CCTV를 처리하기 위해 DFS(cctv_idx + 1, board_copy)를 재귀적으로 호출합니다.

⏱복잡도 분석

• 시간 복잡도:
  • CCTV의 최대 개수는 8개이고, 각 CCTV는 최대 4가지 방향을 가질 수 있습니다. 따라서 가능한 모든 방향 조합의 수는 최대 4^8 입니다. (실제로는 CCTV 종류에 따라 방향 수가 다르므로 이보다는 작습니다)
  • 각 방향 조합에 대해 사무실 전체를 순회하며 사각지대를 계산하므로, O(N*M) 시간이 소요됩니다. 여기서 N과 M은 사무실의 세로 및 가로 크기입니다.
  • 따라서 전체 시간 복잡도는 O(4^8 * N * M) 입니다. N과 M은 최대 8이므로, 대략 O(4^8 * 64) = O(2^16) 정도입니다.
• 공간 복잡도:
  • 사무실 정보를 저장하는 graph 배열의 크기는 O(N*M)입니다.
  • DFS 과정에서 사무실 상태를 복사하는 데 O(N*M) 공간이 필요합니다.
  • 따라서 전체 공간 복잡도는 O(N*M) 입니다.

핵심 포인트

1. 백트래킹 활용: 각 CCTV의 방향을 결정할 때마다 사무실 상태를 복사하여 독립적인 탐색을 수행하고, 이전 상태로 되돌아가는 백트래킹 기법을 사용해야 합니다.
2. deepcopy 사용: 사무실 상태를 복사할 때 copy.deepcopy()를 사용하여 깊은 복사를 수행해야 합니다. 얕은 복사를 사용하면 사무실 상태가 공유되어 백트래킹이 제대로 동작하지 않습니다.
3. 감시 방향 설정: 각 CCTV 종류별 감시 방향 조합을 정확하게 정의하고, detect 함수를 통해 감시 영역을 올바르게 표시해야 합니다.

풀이 코드

import sys
import copy

n, m = map(int, sys.stdin.readline().split())
graph = []
cctvs = []
for i in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    graph.append(row)
    for j in range(m):
        if 1 <= row[j] <= 5:
            cctvs.append((row[j], i, j))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

mode = {
    1: [[0], [1], [2], [3]],
    2: [[0, 2], [1, 3]],
    3: [[0, 1], [1, 2], [2, 3], [3, 0]],
    4: [[0, 1, 3], [0, 1, 2], [1, 2, 3], [0, 2, 3]],
    5: [[0, 1, 2, 3]]
}

min_count = n * m

def detect(board, x, y, direction):
    nx, ny = x, y
    while True:
        nx += dx[direction]
        ny += dy[direction]
        if not (0 <= nx < n and 0 <= ny < m) or board[nx][ny] == 6:
            break
        if board[nx][ny] == 0:
            board[nx][ny] = '#'

def DFS(cctv_idx, graph):
    global min_count

    if cctv_idx == len(cctvs):
        count = 0
        for i in range(n):
            count += graph[i].count(0)
        min_count = min(min_count, count)
        return

    cctv_type, x, y = cctvs[cctv_idx]
    
    for directions in mode[cctv_type]:
        board_copy = copy.deepcopy(graph)
        
        for d in directions:
            detect(board_copy, x, y, d)
            
        DFS(cctv_idx + 1, board_copy)
        

DFS(0, graph)

print(min_count)