○ [파이썬] [구현] 백준 15683 감시

문제

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

15683번: 감시

코드

import sys
from copy import deepcopy

n,m=map(int, input().split())
array=[list(map(int,input().split())) for _ in range(n)]

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

# 0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
# cctv번호, 1 - 90도 회전, 2 - 180도 회전 ...
def dir(cctvNum,i):
    if cctvNum==1:
        return i
    if cctvNum==2:
        if i==0 or i==2:
            return 0,2
        else:
            return 1,3
    if cctvNum==3:
        return (i%4),((i+1)%4)
    if cctvNum==4:
        return (i%4),((i+1)%4),((i+2)%4)
    if cctvNum==5:
        return 0,1,2,3

# cctv 위치 배열에 담기
countC=0
arrayC=[]
for i in range(n):
    for j in range(m):
        if array[i][j] in [1,2,3,4,5]:
            countC+=1
            arrayC.append([i,j])

def dfs(k,arr):
    global result
    if k==countC:
        temp=0
        for i in range(n):
            for j in range(m):
                if arr[i][j]==0:
                    temp+=1
        result=min(result,temp)
        return
    tempArray=deepcopy(arr)
    for i in range(4):
        r,c=arrayC[k]
        cctvNum=array[r][c]
        if cctvNum==1:
            nx, ny = r, c
            while 1:
                nx = nx + dx[i]
                ny = ny + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if tempArray[nx][ny] == 6:
                        break
                    elif tempArray[nx][ny] == 0:
                        tempArray[nx][ny] = '#'
                    else:
                        continue
                else:
                    break
        else:
            for j in dir(cctvNum,i):
                nx,ny=r,c
                while 1:
                    nx=nx+dx[j]
                    ny=ny+dy[j]
                    if 0<=nx<n and 0<=ny<m:
                        if tempArray[nx][ny]==6:
                            break
                        elif tempArray[nx][ny]==0:
                            tempArray[nx][ny]='#'
                        else:
                            continue
                    else:
                        break
        dfs(k+1,tempArray)
        tempArray=deepcopy(arr)

result=sys.maxsize
dfs(0,array)
print(result)

생각 정리

처음에는 dfs()가 끝나고 '#'으로 처리된 부분을 '0'로 바꾸려 했으나 deepcopy 사용하는게 문제 조건에 맞아서 수정하였다.