[Python] 백준 15683번 문제 풀이 - 감시

문제 링크

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

문제 이해

이 문제는 지도와 CCTV와 벽이 주어졌을 때 CCTV가 감시하지 못하는 영역을 최소로 만드는 문제입니다.

CCTV는 5종류가 있습니다.

• 1번 CCTV : 상 하 좌 우 한방향씩만 탐색 가능
• 2번 CCTV : 상하 좌우 두방향씩 탐색 가능
• 3번 CCTV : 상우, 상좌, 하우, 하좌 탐색 가능
• 4번 CCTV : 상하우, 상하좌, 좌우상, 좌우하 탐색 가능
• 5번 CCTV : 상하좌우 탐색 가능

다음 CCTV들이 각각 어떤 방향을 감시할 때 감시하지 못하는 영역이 가장 작아지는지 출력하면 됩니다.

CCTV는 벽 너머는 감시할 수 없고 벽이 없다면 끝까지 감시 가능합니다. 끝까지 가는 중에 CCTV가 있어도 끝까지 감시할 수 있습니다.

아이디어

이 문제를 해결하는 아이디어는 다음과 같습니다. CCTV 개수를 8로 가정하고 하겠습니다.

1. 우선 CCTV 5개의 방향을 저장해둔다.
2. 1번~8번까지 한 방향으로 dfs로 탐색하며 마지막 CCTV까지 탐색한다.
3. 8번 CCTV까지 탐색이 끝났다면 현재 감시하지 못하는 영역이 몇개나 있는지 찾고 최소값을 최신화한다.
4. 그리고 8개의 CCTV의 모든 방향의 조합을 다 해보고 최소값을 출력한다.

시간복잡도

이 아이디어의 시간복잡도는 CCTV가 최대 8개이고 각 CCTV의 방향은 1,3,4번의 경우 최대 4개가 될 수 있으니

4^8이 됩니다. 이것은 2^16으로 바꿀 수 있습니다.

그리고 내부 함수에서 CCTV가 감시할 수 있는 범위를 측정할 때는 최대 8*8에서 수행하기 때문에 한 탐색마다 2^6의 시간이 걸립니다. 그러면 총 시간복잡도는 2^22으로 400만정도가 나와서 가능합니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

import copy

n, m = map(int, input().split())
cctv = []
board = []

mode = [
    [],
    [[0], [1], [2], [3]], # 1번 cctv
    [[0,2], [1,3]], # 2번 cctv
    [[0,1], [1,2], [2,3], [0,3]], # 3번 cctv
    [[0,1,2], [0,1,3], [1,2,3], [0,2,3]], # 4번 cctv
    [[0,1,2,3]] # 5번 cctv
]

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

# 보드 넣기
for i in range(n):
    data = list(map(int, input().split()))
    board.append(data)

    # 넣는 중 CCTV 발견되면 CCTV 배열에 추가
    for j in range(m):
        if data[j] in [1,2,3,4,5]:
            cctv.append([data[j], i, j])

# cctv가 감지하는 범위 확인하는 함수
def fill(board, mode, x, y):
    # 3번 cctv면 mode : [[0,1], [1,2], [2,3], [0,3]]
    for i in mode:
        nx = x
        ny = y
        while True:
            # 이동방향으로 쭉 이동
            nx += dx[i]
            ny += dy[i]

            # 범위 나가면 끝
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break

            # 벽이면 끝
            if board[nx][ny] == 6:
                break

            # 만약에 탐지 가능하면 -1로 탐지했다는 표시
            elif board[nx][ny] == 0:
                board[nx][ny] = -1

# CCTV가 탐지할 수 있는 모든 경우의 수 구하는 함수
def dfs(depth, board):
    global min_value
    # 전체 CCTV 다 탐색했을 경우
    if depth == len(cctv):
        count = 0
        # 탐지 안된 구역 세고
        for i in range(n):
            count += board[i].count(0)

        # 가장 적게 탐지가 된 구역 최신화
        min_value = min(min_value, count)
        return


    temp = copy.deepcopy(board) # 이전 CCTV 탐색한 맵 가져오기
    cctv_num, x, y = cctv[depth] # 현재 CCTV 종류와 좌표 가져오기
    for i in mode[cctv_num]:
        fill(temp, i, x, y) # 현재 CCTV 감지 범위 확인
        dfs(depth+1, temp) # 다음 CCTV에 현재 감지한 범위의 배열 넣어주기
        temp = copy.deepcopy(board) # 위의 함수에서 길이가 8로 다 돌았으면 7번째의 지도로 바꾼 후에 8번 CCTV의 다음 방향 탐색

min_value = 64
dfs(0, board)
print(min_value)

느낀 점

아이디어는 떠올렸는데 방향을 어떻게 설정해야할지 감이 안왔고, 어떻게 모든 CCTV의 방향을 탐색 할 수 있을지에 대한 코드 구현 능력이 부족했습니다.

그래서 다음 블로그를 참고하여 코드를 참고하여 이해하는 방식으로 문제를 풀었습니다.

https://yeon-code.tistory.com/76

[python] BOJ 백준 15683: 감시

 

재귀함수와 백트래킹을 다른 사람의 코드를 보고 겨우 이해는 하겠지만 직접 짤 때는 어떻게 짜야할지 아직 감이 안와서 문제를 더 풀어보며 아이디어를 떠올릴 수 있게 많이 풀어봐야 할 듯합니다.