[백준][Python] 15638번 감시 - 재귀

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

15683번: 감시

 

 

 

 

Python

import sys
from collections import deque
input = sys.stdin.readline

answer = float("inf")
n, m = map(int, input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
cctv = [(i,j) for j in range(m) for i in range(n) if 0<arr[i][j]<6]


dx, dy = [0, 0, 1, 0, -1], [0, -1, 0 , 1, 0]
direction = [
    [],
    [(0, 1),(0, 2),(0, 3),(0, 4)],
    [(1,3),(2,4)],
    [(1,2),(2,3),(3,4),(1,4)],
    [(1,2,3),(2,3,4),(1,3,4),(1,2,4)],
    [(1,2,3,4)]
]



def back(zidx):
    global arr,cctv,direction,answer
    if zidx == len(cctv):
        temp = 0
        
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 0:
                    temp += 1
        answer = min(answer, temp)
        return

    x, y = cctv[zidx]
    for dd in direction[arr[x][y]]:
        original = dict()
        for d in dd:
            nx, ny = x+dx[d], y+dy[d]
            if d==0 or nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            original[d] = deque()
            while 0<=nx<n and 0<=ny<m:
                if arr[nx][ny] == 6:
                    break
                original[d].append(arr[nx][ny])
                arr[nx][ny] = 7 if arr[nx][ny] == 0 else arr[nx][ny]
                nx, ny = nx+dx[d], ny+dy[d]
        back(zidx+1)
        for d in dd:
            nx, ny = x+dx[d], y+dy[d]
            if d==0 or nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            while original[d]:
                arr[nx][ny] = original[d].popleft()
                nx, ny = nx+dx[d], ny+dy[d]

back(0)
print(answer)