BOJ - 감시 15683번 (python)

❓ 문제 - 백준 감시 15683번 - python 풀이법

출처 

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

15683번: 감시

 

 

 

📝 문제해결법

1. 이 문제는 DFS+구현으로 풀었다.

• mode라는 리스트로 CCTV의 종류(1, 2, 3, 4, 5)에 따라 회전했을 때 바라보는 방향을 넣어준다.
• 사무실의 정보를 입력받을 때, cctv의 종료 및 위치(i,j)를 cctv 리스트에 append한다.
• DFS를 돌려서 해당 cctv의 종류의 각도로 감시를 실행한 후,  cctv 갯수만큼 CCTV로 감시를 다 했을 때 사각지대의 최솟값을 갱신한다.
• fill() : 해당 CCTV의 종류에서 바라보는 방향에 따라 감시할 수 있는 곳은 다 7로 변환시켜 감시하고, 만약 벽을 만나거나 범위를 넘는 곳을 탐색하면 while 문을 빠져 나와 감시를 종료한다.

 

 

💻 소스코드

import copy
n, m = map(int, input().split())
cctv = []
graph = []
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]],
]

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

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if data[j] in [1, 2, 3, 4, 5]:
            cctv.append([data[j], i, j])

def fill(board, mm, x, y):
    for i in mm:
        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
            elif board[nx][ny] == 0:
                board[nx][ny] = 7

def dfs(depth, arr):
    global min_value

    if depth == len(cctv):
        count = 0
        for i in range(n):
            count += arr[i].count(0)
        min_value = min(min_value, count)
        return
    temp = copy.deepcopy(arr)
    cctv_num, x, y = cctv[depth]
    for i in mode[cctv_num]:
        fill(temp, i, x, y)
        dfs(depth+1, temp)
        temp = copy.deepcopy(arr)


min_value = int(1e9)
dfs(0, graph)
print(min_value)