문제
https://www.acmicpc.net/problem/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 사용하는게 문제 조건에 맞아서 수정하였다.
'문제풀이 > 구현' 카테고리의 다른 글
● [파이썬] [구현] 백준 17144 미세먼지 안녕! (0) | 2023.03.29 |
---|---|
● [파이썬] [구현] 백준 15685 드래곤 커브 (0) | 2023.03.28 |
○ [파이썬] [구현] 백준 14499 주사위 굴리기 (0) | 2023.03.25 |
● [파이썬] [구현] 백준 21610 마법사 상어와 비바라기 (0) | 2023.03.22 |
@ [파이썬] [구현] 백준 21608 상어 초등학교 (0) | 2023.03.20 |