구현 자체는 어렵다기 보다는 양이 많다.
벽을 만나기 전까지 값을 바꿔주면서 cctv의 갯수만큼 재귀를 하면 된다.
구현 중 실수:
1. [0] 까지도 탐색을 했어야 하는데, while(dy > 0): 이렇게 와일문에 등호를 빼먹어서 완전탐색 실패
2. 기준이 되는 값에 따라 봐야할 방향이 다 다른데 그냥 무지성으로 1로 체크를 했음
ㄴ> 카메라가 있으면 관통은 하돼, 카메라값을 바꿔서는 안됌
구현 부
import sys
import copy
from collections import deque
n,m = input().split()
n=int(n)
m=int(m)
origin = []
#이후 배열의 깊은 복사를 사용하자
for _ in range(n):
origin.append(list(map(int,sys.stdin.readline().strip().split())))
cctvarr = []
cnt = 0
for i in range(n):
for j in range(m):
if origin[i][j] > 0:
if origin[i][j] < 6:
cctvarr.append([i,j])
cnt+=1
#5번으로 받는 경우 dir =0, 2의 가로는1 세로는 2,
\# 3은 1은 ㄴ모양, 2는 1의 x축대칭, 3은 ㄱ, 4는 3의 x축 대칭
\# 4는 우1 하2 좌3 상4
\# 1도 동일
def change(arr,b,a,dir): ###bfs를 할게 아니라 방향에 따라 그냥 선회하도록 짜는게 맞는 거 같음
new = copy.deepcopy(arr)
if new[b][a] == 5: #dir 0
dx = a
while(dx < m):
if new[b][dx] ==0:
new[b][dx] = 5
elif new[b][dx] == 6:
break
dx+=1
dx = a#else
while(dx >= 0):
if new[b][dx] ==0:
new[b][dx] = 5
elif new[b][dx] == 6:
break
dx-=1
dy = b
while(dy >= 0):
if new[dy][a] ==0:
new[dy][a] = 5
elif new[dy][a] == 6:
break
dy-=1
dy = b
while(dy < n):
if new[dy][a] ==0:
new[dy][a] = 5
elif new[dy][a] == 6:
break
dy+=1
elif new[b][a] == 2: #dir 1,2만
if dir == 1: #<>
dx = a
while(dx < m):
if new[b][dx] ==0:
new[b][dx] = 2
elif new[b][dx] == 6:
break
dx+=1
dx = a
while(dx >= 0):
if new[b][dx] ==0:
new[b][dx] = 2
elif new[b][dx] == 6:
break
dx-=1
elif dir == 2:
dy = b
while(dy < n):
if new[dy][a] ==0:
new[dy][a] = 2
elif new[dy][a] == 6:
break
dy+=1
dy = b
while(dy >= 0):
if new[dy][a] ==0:
new[dy][a] = 2
elif new[dy][a] == 6:
break
dy-=1
elif new[b][a] == 3: # 3은 1은 ㄴ모양, 2는 1의 x축대칭, 3은 ㄱ, 4는 3의 x축 대칭
if dir == 1:
dy = b
while(dy >= 0):
if new[dy][a] ==0:
new[dy][a] = 3
elif new[dy][a] == 6:
break
dy -= 1
dx = a
while(dx < m):
if new[b][dx] ==0:
new[b][dx] = 3
elif new[b][dx] == 6:
break
dx += 1
if dir == 2:
dy = b
while(dy < n):
if new[dy][a] ==0:
new[dy][a] = 3
elif new[dy][a] == 6:
break
dy += 1
dx = a
while(dx < m):
if new[b][dx] == 0:
new[b][dx] = 3
elif new[b][dx] == 6:
break
dx += 1
if dir == 3:
dy = b
while(dy < n):
if new[dy][a] ==0:
new[dy][a] = 3
elif new[dy][a] == 6:
break
dy += 1
dx = a
while(dx >= 0):
if new[b][dx] ==0:
new[b][dx] = 3
elif new[b][dx] == 6:
break
dx -= 1
if dir == 4:
dy = b
while(dy >= 0):
if new[dy][a] ==0:
new[dy][a] = 3
elif new[dy][a] == 6:
break
dy -= 1
dx = a
while(dx >= 0):
if new[b][dx] == 0:
new[b][dx] = 3
elif new[b][dx] == 6:
break
dx -= 1
elif new[b][a] == 4: # 4는 우1 하2 좌3 상4
if dir == 1:
dy = b
while(dy >= 0):
if new[dy][a] == 0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy -= 1
dx = a
while(dx < m):
if new[b][dx] == 0:
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx += 1
dy = b
while(dy < n):
if new[dy][a] == 0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy += 1
if dir == 2:
dy = b
while(dy < n):
if new[dy][a] == 0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy += 1
dx = a
while(dx < m):
if new[b][dx] == 0:
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx += 1
dx = a
while(dx >= 0):
if new[b][dx] ==0:
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx -= 1
if dir == 3:
dy = b
while(dy < n):
if new[dy][a] ==0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy += 1
dx = a
while(dx >= 0):
if new[b][dx] == 0 :
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx -= 1
dy = b
while(dy >= 0):
if new[dy][a] == 0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy -= 1
if dir == 4:
dy = b
while(dy >= 0):
if new[dy][a] == 0:
new[dy][a] = 4
elif new[dy][a] == 6:
break
dy -= 1
dx = a
while(dx >= 0):
if new[b][dx] == 0:
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx -= 1
dx = a
while(dx < m):
if new[b][dx] == 0:
new[b][dx] = 4
elif new[b][dx] == 6:
break
dx += 1
elif new[b][a] == 1: #우1 하2 좌3 상4
if dir == 1:
dx = a
while(dx < m):
if new[b][dx] == 0:
new[b][dx] = 1
elif new[b][dx] == 6:
break
dx+=1
if dir == 3:
dx = a
while(dx >= 0):
if new[b][dx] == 0:
new[b][dx] = 1
elif new[b][dx] == 6:
break
dx-=1
if dir == 4:
dy = b
while(dy >= 0):
if new[dy][a] == 0:
new[dy][a] = 1
elif new[dy][a] == 6:
break
dy-=1
if dir == 2:
dy = b
while(dy < n):
if new[dy][a] == 0:
new[dy][a] = 1
elif new[dy][a] == 6:
break
dy+=1
return new
def simul(arr, cctvarr, cnt, checked):
if cnt == checked:
mini = 0
for h in range(n):
for w in range(m):
if arr[h][w] == 0:
mini+=1
return mini
# if checked == 1:
# print("s")
mmin = 100
y, x = cctvarr[checked]
if arr[y][x] == 5:
newarr = change(arr,y,x,0) #숫자 확인하고, 숫자에 따라 값을 변경 위의 이프문 필요한지 생각은 필요하다
mmin = simul(newarr, cctvarr, cnt, checked + 1)
if (arr[y][x] == 4) or (arr[y][x] == 3) or (arr[y][x] == 1):
newarr = change(arr,y,x,1)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
newarr = change(arr,y,x,2)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
newarr = change(arr,y,x,3)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
newarr = change(arr,y,x,4)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
if arr[y][x] == 2:
newarr = change(arr,y,x,1)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
newarr = change(arr,y,x,2)
temp = simul(newarr, cctvarr, cnt, checked + 1)
if temp <= mmin:
mmin = temp
return mmin
print(simul(origin, cctvarr, cnt, 0))#1. 0을 고려하지 않음 while (d>=0) bfs,dfs나 똑같음 0은 등호붙고 n,m은 안붙는 것 주의
#2. 고유의 값으로 탐색하는데 그걸 바꿔버리면 될리가 없음 >>> 내가 기준으로 삼을 것 까지 바꾸지 않아야 함
42Seoul