[백준] 15683번 감시 - 파이썬

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

15683번: 감시

import sys
import copy
n, m = map(int,sys.stdin.readline().split())
room = []
cctv = []
for i in range(n):
    info = list(map(int,sys.stdin.readline().split()))
    room.append(info)
    for j in range(len(info)):
        if info[j] in [1,2,3,4,5]:
            cctv.append([info[j],i,j])
direction = [
    [],
    [[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]

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
    tmp= copy.deepcopy(arr)
    cctv_num , x, y = cctv[depth]
    for i in direction[cctv_num]:
        fill(tmp,i,x,y)
        dfs(depth+1,tmp)
        tmp = copy.deepcopy(arr)

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

문제의 풀이를 

https://developer-ellen.tistory.com/53

BOJ - 감시 15683번 (python)

이분 블로그 참고하고 풀었다.

문제를 접근할때 dfs를 생각 못했는데 참고하고 바로 풀었고

direction을 어떻게 돌려야 될까? 라고 생각을 했는데

direction = [
    [],
    [[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]],
]

이 아이디어를 보고 깜짝 놀랐다. 이미 정해저있는건 만들어 두고 하는거 꼭 생각하자

 

나머지 dfs는 우리가 알고 있는 일반적인 방법이랑 비슷하다 탈출 조건 정해주고 재귀해주고하면 풀 수 있는 문제이다

문제에 대한 접근과 생각을 꼭 잘해보자