[python] 백준 15683 감시

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

15683번: 감시

 

문제 해결

• 문제가 많이 어려웠다.(다른 분들의 풀이를 참고했다.)
• 결국 cctv 종류당 이동할 수 있는 방법의 수가 정해져 있기 때문에 dfs, bfs를 이용한 완전탐색을 해야한다.
• 이 사실을 알고 cctv당 이동 할 수 있는 방법을 리스트 안에 구현을 하면 사실 끝이다.
• 완전 탐색 후 가장 적게 사각지대가 생긴 개수를 구하면 된다.

 

CODE

import sys 
input = sys.stdin.readline
import copy
INF = sys.maxsize


def dfs(graph, cnt):
    global ans
    # 종료 조건: 모든 CCTV 탐색
    if cnt == len(cctv_list):
        # 사각지대 최솟값
        ans = min(ans, count_zero(graph))
        return
    else:
        graph_copy = copy.deepcopy(graph)
        x, y, cctv_type = cctv_list[cnt]
        for cctv_dir in cctv_direction[cctv_type]:
            # CCTV 감시영역 구하는 함수 호출
            watch(x, y, cctv_dir, graph_copy)
            dfs(graph_copy, cnt + 1)
            # CCTV를 다른 방향으로 회전시킨 후 재탐색하기 위함
            graph_copy = copy.deepcopy(graph)

# CCTV 감시영역 구하는 함수
def watch(x, y, direction, graph):
    for d in direction:
        while True:
            nx = x + move[d][0]
            ny = y + move[d][1]
            if 0 <= nx < n and 0 <= ny < m:
                # 벽을 만난 경우
                if graph[nx][ny] == 6:
                    break
                # 새로운 감시가능 영역일 경우
                elif graph[nx][ny] == 0:
                    graph[nx][ny] = '#'
            else:
                break

# 사각지대 개수 구하는 함수
def count_zero(graph):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                cnt += 1
    return cnt

if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    ans = INF # 최솟값 구하기
    cctv_list = [] # CCTV 좌표 저장
    for i in range(n):
        for j in range(m):
            if 1 <= graph[i][j] <= 5: # cctv 위치에 도달
                cctv_list.append((i, j, graph[i][j]))
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # CCTV별 이동 가능한 방향
    cctv_direction = [
        [],
        [[0], [1], [2], [3]], # 1번 CCTV
        [[0, 1], [2, 3]], # 2번 CCTV
        [[0, 2], [0, 3], [1, 2], [1, 3]], # 3번 CCTV
        [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], # 4번 CCTV
        [[0, 1, 2, 3]] # 5번 CCTV
    ]
    dfs(graph, 0)
    print(ans)