[Baekjoon] 15683번 : 감시 - Python

Gold 5

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

15683번: 감시

문제 풀이

오랜만에 dfs 유형! + 구현

각 카메라마다 볼 수 있는 방향들을 리스트로 만들어주고 dfs로 탐색해준다.

 

코드

from copy import deepcopy

n, m = map(int, input().split())
office, cctv = [], []
min_value = 1e9

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


# 각 카메라별로 볼 수 있는 방향 설정
camera = [[],
          [[0], [1], [2], [3]],
          [[0, 2], [1, 3]],
          [[0, 1], [1, 2], [0, 3], [2, 3]],
          [[0, 1, 2], [1, 2, 3], [0, 2, 3], [0, 1, 3]],
          [[0, 1, 2, 3]]]


mx = [1, 0, -1, 0]
my = [0, -1, 0, 1]

def on_cctv(direction, x, y, arr):
    for d in direction:
        nx, ny = x, y
        while True:
            nx += mx[d]
            ny += my[d]

            if 0 > nx or nx >= n or ny < 0 or ny >= m:
                break
            if arr[nx][ny] == 6:
                break
            elif arr[nx][ny] == 0:
                arr[nx][ny] = 7


def solution(num, arr):
    global min_value

    # cctv 개수 모두 탐색이 완료되면 중단
    if num == len(cctv):
        count = 0
        for i in range(n):
            count += arr[i].count(0)
        min_value = min(count, min_value)
        return

    # 값만 복사 하도록 deepcopy
    temp_office = deepcopy(arr)

    # cctv번호와 좌표
    cctv_num, x, y = cctv[num]
    for direction in camera[cctv_num]:
        on_cctv(direction, x, y, temp_office)
        solution(num+1, temp_office)
        # 다시 원상 복귀
        temp_office = deepcopy(arr)


solution(0, office)
print(min_value)