백준 감시 [15683] 파이썬(Python) 코드 + 해설

백준 15683 감시 문제

 

문제 설명

• 사무실은 N×M 크기의 격자로 표현됩니다.
  • N,M ≤ 8이므로 격자의 크기는 최대 8 × 8 입니다.
• 격자의 각 칸에는 다음 중 하나가 있습니다:
  • 빈 칸 (0): 아무것도 없는 공간입니다.
  • 벽 (6): CCTV의 시야를 가로막는 벽입니다.
  • CCTV (1~5): CCTV 카메라가 설치되어 있습니다.
    • CCTV는 총 5가지 종류가 있으며, 각 종류마다 감시할 수 있는 방향이 다릅니다.
• 목표: CCTV의 방향을 적절히 설정하여 사각지대(감시되지 않는 영역)의 최소 크기를 구하는 것입니다.

CCTV 종류 및 감시 방향

CCTV의 종류에 따라 감시할 수 있는 방향이 정해져 있습니다:

1. 1번 CCTV: 한 방향 감시 (총 4가지 경우)
2. 2번 CCTV: 두 방향 감시 (서로 반대 방향, 총 2가지 경우)
3. 3번 CCTV: 두 방향 감시 (직각 방향, 총 4가지 경우)
4. 4번 CCTV: 세 방향 감시 (총 4가지 경우)
5. 5번 CCTV: 네 방향 감시 (경우의 수 1개)

감시 규칙

• CCTV는 감시하는 방향에 있는 벽을 만나기 전까지의 모든 칸을 감시할 수 있습니다.
• CCTV는 벽을 통과할 수 없지만, 다른 CCTV는 통과할 수 있습니다.
• CCTV의 방향은 90도 단위로 회전시킬 수 있습니다.
• CCTV의 방향을 설정하여 사각지대의 최소 크기를 구해야 합니다.

해결 전략

• 완전 탐색(백트래킹)을 사용하여 모든 가능한 CCTV의 방향 조합을 시도합니다.
• CCTV의 개수가 최대 8개이므로, 각 CCTV의 가능한 방향 수를 곱하더라도 경우의 수는 최대 4^8=65,536입니다.
• 각 조합마다 CCTV의 감시 영역을 시뮬레이션하고, 사각지대의 크기를 계산하여 최소값을 갱신합니다.

단계별 구현

1. 입력 처리 및 초기화:
   • 사무실의 크기 N, M과 격자 정보를 입력받습니다.
   • CCTV의 위치와 종류를 저장합니다.
2. CCTV의 가능한 방향 조합 생성:
   • 각 CCTV의 종류에 따라 가능한 감시 방향을 리스트로 저장합니다.
     • 1번 CCTV: [상],[하],[좌],[우][상], [하], [좌], [우][상],[하],[좌],[우]
     • 2번 CCTV: [상,하],[좌,우][상, 하], [좌, 우][상,하],[좌,우]
     • 3번 CCTV: [상,우],[우,하],[하,좌],[좌,상][상, 우], [우, 하], [하, 좌], [좌, 상][상,우],[우,하],[하,좌],[좌,상]
     • 4번 CCTV: [좌,상,우],[상,우,하],[우,하,좌],[하,좌,상][좌, 상, 우], [상, 우, 하], [우, 하, 좌], [하, 좌, 상][좌,상,우],[상,우,하],[우,하,좌],[하,좌,상]
     • 5번 CCTV: [상,하,좌,우][상, 하, 좌, 우][상,하,좌,우]
3. 백트래킹을 통한 모든 경우의 수 탐색:
   • 재귀 함수를 사용하여 각 CCTV의 가능한 방향을 선택하고 다음 CCTV로 넘어갑니다.
   • 모든 CCTV의 방향이 결정되면 시뮬레이션을 수행합니다.
4. 시뮬레이션:
   • CCTV의 방향에 따라 감시 영역을 표시합니다.
     • 격자에 감시 영역을 표시하기 위해 복사본을 만들어 사용합니다.
     • 감시 영역은 벽(6)을 만나기 전까지 계속 확장됩니다.
   • 감시 영역을 표시한 후 사각지대의 크기를 계산합니다.
5. 사각지대의 최소값 갱신:
   • 각 경우의 시뮬레이션 결과에서 사각지대의 크기를 계산하고 최소값을 갱신합니다.
6. 결과 출력:
   • 모든 경우를 탐색한 후 최소 사각지대 크기를 출력합니다.

 

파이썬 정답 코드

import sys
import copy
input = sys.stdin.readline

# 사무실 크기 입력
N, M = map(int, input().split())
office = []
cctv = []

# 방향 설정 (상, 우, 하, 좌)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# CCTV 종류별 가능한 방향
cctv_directions = {
    1: [[0], [1], [2], [3]],
    2: [[0, 2], [1, 3]],
    3: [[0, 1], [1, 2], [2, 3], [3, 0]],
    4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    5: [[0, 1, 2, 3]]
}

# 사무실 정보 입력 및 CCTV 위치 저장
for i in range(N):
    row = list(map(int, input().split()))
    office.append(row)
    for j in range(M):
        if 1 <= row[j] <= 5:
            cctv.append((i, j, row[j]))

min_blind_spot = N * M  # 사각지대의 최소값 초기화

def watch(x, y, directions, temp_office):
    for d in directions:
        nx, ny = x, y
        while True:
            nx += dx[d]
            ny += dy[d]
            if 0 <= nx < N and 0 <= ny < M:
                if temp_office[nx][ny] == 6:
                    break  # 벽이면 종료
                elif temp_office[nx][ny] == 0:
                    temp_office[nx][ny] = '#'  # 감시 영역 표시
            else:
                break  # 범위를 벗어나면 종료

def dfs(depth, office_map):
    global min_blind_spot
    if depth == len(cctv):
        # 사각지대 계산
        blind_spot = 0
        for row in office_map:
            blind_spot += row.count(0)
        min_blind_spot = min(min_blind_spot, blind_spot)
        return

    temp_office = copy.deepcopy(office_map)
    x, y, cctv_type = cctv[depth]
    for directions in cctv_directions[cctv_type]:
        watch(x, y, directions, temp_office)
        dfs(depth + 1, temp_office)
        temp_office = copy.deepcopy(office_map)  # 복원

dfs(0, office)
print(min_blind_spot)

코드 설명

입력 처리 및 초기화

• N, M: 사무실의 세로, 가로 크기.
• office: 사무실의 상태를 저장하는 2차원 리스트.
• cctv: CCTV의 위치와 종류를 저장하는 리스트.
• dx, dy: 방향을 나타내는 리스트 (상, 우, 하, 좌).
• cctv_directions: CCTV 종류별로 가능한 감시 방향을 정의한 딕셔너리.

watch 함수

• 특정 CCTV가 감시하는 영역을 표시하는 함수입니다.
• 입력된 방향에 따라 CCTV의 감시 영역을 확장하고, 감시 영역은 '#'로 표시합니다.
• 벽(6)을 만나거나 사무실 범위를 벗어나면 감시를 중단합니다.

dfs 함수 (백트래킹)

• depth: 현재 처리 중인 CCTV의 인덱스.
• office_map: 현재 사무실의 상태.
• 모든 CCTV의 방향이 결정되면 사각지대의 크기를 계산하고 최소값을 갱신합니다.
• 각 CCTV의 가능한 방향에 대해 재귀적으로 다음 CCTV를 처리합니다.
• 재귀 호출 후에는 사무실 상태를 복원하여 다음 경우의 수를 정확히 시뮬레이션합니다.

결과 출력

• 모든 경우의 수를 탐색한 후, min_blind_spot 값을 출력하여 최소 사각지대의 크기를 구합니다.

 

백준 15683 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다.