[알고리즘] 감시 python (백준 15683)

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

 

CCTV 감시 문제 풀이 설명

1. 문제 개요

• N×M 크기의 사무실에 여러 대의 CCTV가 설치되어 있음
• CCTV는 1~5번까지 5종류가 있으며, 각각 감시할 수 있는 방향이 다름
• CCTV는 90도씩 회전 가능하며, 벽을 통과할 수 없음
• 목표: CCTV 방향을 적절히 조절하여 사각지대를 최소화

2. 주요 자료구조 설명

CCTV 방향 정의

dirs = {
    1: [[(1, 0)], [(0, 1)], [(-1, 0)], [(0, -1)]],           # 1번 CCTV: 한 방향
    2: [[(1, 0), (-1, 0)], [(0, 1), (0, -1)]],              # 2번 CCTV: 양방향
    3: [[(-1, 0), (0, 1)], [(0, 1), (1, 0)], ...],          # 3번 CCTV: 직각 방향
    4: [[(0, -1), (-1, 0), (0, 1)], ...],                   # 4번 CCTV: 세 방향
    5: [[(0, 1), (1, 0), (-1, 0), (0, -1)]]                 # 5번 CCTV: 네 방향
}

• 각 CCTV 종류별로 가능한 방향 조합을 딕셔너리로 정의
• 각 방향은 (dx, dy) 형태의 튜플로 표현

3. 핵심 함수 설명

3.1 감시 영역 표시 함수

def next(row, col, dir, curVal):
    nextRow, nextCol = row + dir[0], col + dir[1]
    if 0 <= nextRow < N and 0 <= nextCol < M and board[nextRow][nextCol] != 6:
        board[nextRow][nextCol] += curVal
        next(nextRow, nextCol, dir, curVal)

• 재귀적으로 한 방향의 모든 칸을 감시
• curVal: 1(감시 추가) 또는 -1(감시 제거)로 사용
• 벽(6)을 만나거나 경계를 벗어나면 중단

3.2 CCTV 처리

# 5번 CCTV 먼저 처리 (회전이 필요 없음)
c5 = list(filter(lambda x: board[x[0]][x[1]] == 5, cctvs))
cctvs = list(filter(lambda x: board[x[0]][x[1]] != 5, cctvs))
for row, col, _ in c5:
    for nexts in dirs[5]:
        for nextDir in nexts:
            next(row, col, nextDir, 1)

• 5번 CCTV는 회전이 의미 없으므로 먼저 처리
• 나머지 CCTV는 이후 DFS로 처리

3.3 DFS 탐색

def dfs(depth):
    nonlocal res
    if depth == len(cctvs):
        temp = 0
        for row in range(N):
            for col in range(M):
                if board[row][col] == 0:
                    temp += 1
        res = min(res, temp)
        if res == 0:
            print(0)
            exit(0)
        return

    row, col, dirInd = cctvs[depth]
    curDir = dirs[dirInd]
    for nexts in curDir:
        for nextDir in nexts:
            next(row, col, nextDir, 1)  # 감시 영역 표시
        dfs(depth + 1)
        for nextDir in nexts:
            next(row, col, nextDir, -1)  # 감시 영역 제거

• 각 CCTV의 모든 가능한 방향 조합을 시도
• 백트래킹을 사용하여 이전 상태로 복구
• 모든 CCTV 방향이 결정되면 사각지대 개수 계산

4. 시간 복잡도

• CCTV 최대 개수: 8개
• 각 CCTV당 최대 4방향
• 전체 시간 복잡도: O(4^8 * N * M)
  • 4^8: 모든 CCTV 방향 조합
  • N * M: 각 조합에서 사각지대 계산

5. 주요 최적화 포인트

1. 5번 CCTV 먼저 처리로 탐색 공간 감소
2. 사각지대가 0인 경우 즉시 종료
3. 백트래킹으로 불필요한 탐색 방지

코드

import sys
input = sys.stdin.readline

def sol() :
    N, M = list(map(int, input().split()))
    board = [list(map(int, input().split())) for _ in range(N)]
    dirs = {
        1: [
            [(1, 0)],
            [(0, 1)],
            [(-1, 0)],
            [(0, -1)]
        ],
        2: [
            [(1, 0), (-1, 0)],
            [(0, 1), (0, -1)]
        ],
        3: [
            [(-1, 0), (0, 1)],
            [(0, 1), (1, 0)],
            [(1, 0), (0, -1)],
            [(0, -1), (-1, 0)]
        ],
        4: [
            [(0, -1), (-1, 0), (0, 1)],
            [(-1, 0), (0, 1), (1, 0)],
            [(0, 1), (1, 0), (0, -1)],
            [(1, 0), (0, -1), (-1, 0)],
        ],
        5: [
            [(0, 1), (1, 0), (-1, 0), (0, -1)]
        ]
    }

    def next(row, col, dir, curVal):
        nextRow, nextCol = row + dir[0], col + dir[1]
        if 0 <= nextRow < N and 0 <= nextCol < M and board[nextRow][nextCol] != 6:
            board[nextRow][nextCol] += curVal
            next(nextRow, nextCol, dir, curVal)

    cctvs = []
    for row in range(N) :
        for col in range(M) :
            if board[row][col] != 6 and board[row][col] != 0:
                cctvs.append((row, col, board[row][col]))

    c5 = list(filter(lambda x: board[x[0]][x[1]] == 5, cctvs))
    cctvs = list(filter(lambda x: board[x[0]][x[1]] != 5, cctvs))
    for row, col, _ in c5:
        for nexts in dirs[5] :
            for nextDir in nexts :
                next(row, col, nextDir, 1)

    res = sys.maxsize
    def dfs(depth) :
        nonlocal res
        if depth == len(cctvs) :
            temp = 0
            for row in range(N):
                for col in range(M):
                    if board[row][col] == 0 :
                        temp += 1
            res = min(res, temp)
            if res == 0:
                print(0)
                exit(0)
            return

        row, col, dirInd = cctvs[depth]
        curDir = dirs[dirInd]
        for nexts in curDir:
            for nextDir in nexts:
                next(row, col, nextDir, 1)
            dfs(depth + 1)
            for nextDir in nexts:
                next(row, col, nextDir, -1)

    dfs(0)
    print(res)

sol()