import copy
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
#cctv 리스트를 만듬 (종류, 좌표)
cctv = []
for i in range(n):
for j in range(m):
if 1 <= g[i][j] <= 5:
cctv.append((g[i][j], i, j))
rotate = [[[0], [1], [2], [3]], #1번 cctv가 가질 수 있는 방향 조합
[[0, 2], [1, 3]], #2번 cctv가 가질 수 있는 방향 조합 rotate[1][0~2]
[[3, 0], [0, 1], [1, 2], [2, 3]],#3번 cctv가 가질 수 있는 방향 조합 rotate[2][0~4]
[[2, 3, 0], [3, 0, 1], [0, 1, 2], [1, 2, 3]],
[[0, 1, 2, 3]]
]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def change(x, y, d, g):
# 일단 (x, y)에는 cctv 가 있다.
# 방향 받아서 그 방향으로 다음 칸이 빈칸이면 -1로 바꿔줌
nx, ny = x + dx[d], y + dy[d]
# 다음 확인할 칸이 경계를 넘거나 빈칸이 아니라면 검사 끝남 return 해줌
if nx < 0 or ny < 0 or nx >= n or ny >= m:
return g
elif g[nx][ny] == 6:
return g
else:
# 빈칸이면 -1로 바꿈
g[nx][ny] = -1
# 빈칸이면 그 다음도 감시 가능한지 알아본다
change(nx, ny, d, g)
# 최종적으로 출력할 결과 값
ans = n * m + 1
# cctv의 index를 변경시켜 가며 g를 바꿔나감
def dfs(index, g):
global ans, n, m
# 만약 cctv를 전부다 고려했다면 사각지대의 갯수를 센 다음 ans를 업데이트한다
if index == len(cctv):
cnt = 0
for i in range(n):
for j in range(m):
if g[i][j] == 0:
cnt += 1
if cnt < ans:
ans = cnt
return ans
# cctv 의 타입별로 , 90도 회전하며 방향 조합 별로 탐색
cctvtype, x, y = cctv[index]
# cctv 타입 별로 가능한 조합
for arrows in rotate[cctvtype-1]:
# 이 전의 그래프를 deepcopy해둠 -> 방향 별로 g가 달라질거니까
tmp_g = copy.deepcopy(g)
for arrow in arrows:
tmp_g = change(x, y, arrow, tmp_g)
# 방향별로 감시 가능 영역을 다 -1로 표시함
# 인덱스 늘려서 dfs해서 다음 cctv에 대한 감시 가능 영역을 표시한다
dfs(index+1, tmp_g)
dfs(0, g)
print(ans)처음에 이런 코드를 짰었는데
자꾸 TypeError: 'NoneType' object is not subscriptable 가 나와서 뭔가 한참 찾았는데 change 함수에서 return 값이 none이 나오는 경우가 생김
계속 재귀를 들어가고 끝내지 못한다면 return 값을 찾을 수 없는 문제가 생긴다(????)
->재귀함수만(?)의 반환값이 필요 아니면 걍 리턴값을 없애든지 일관성이 필요하다
<<잘 이해 안됨
import copy
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
#cctv 리스트를 만듬 (종류, 좌표)
cctv = []
for i in range(n):
for j in range(m):
if 1 <= g[i][j] <= 5:
cctv.append((g[i][j], i, j))
rotate = [[[0], [1], [2], [3]], #1번 cctv가 가질 수 있는 방향 조합
[[0, 2], [1, 3]], #2번 cctv가 가질 수 있는 방향 조합 rotate[1][0~2]
[[3, 0], [0, 1], [1, 2], [2, 3]],#3번 cctv가 가질 수 있는 방향 조합 rotate[2][0~4]
[[2, 3, 0], [3, 0, 1], [0, 1, 2], [1, 2, 3]],
[[0, 1, 2, 3]]
]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def change(x, y, d, g):
# 일단 (x, y)에는 cctv 가 있다.
# 방향 받아서 그 방향으로 다음 칸이 빈칸이면 -1로 바꿔줌
nx, ny = x + dx[d], y + dy[d]
# 다음 확인할 칸이 경계를 넘거나 빈칸이 아니라면 검사 끝남 return 해줌
if nx < 0 or ny < 0 or nx >= n or ny >= m:
return
elif g[nx][ny] == 6:
return
else:
# 빈칸이면 -1로 바꿈
g[nx][ny] = -1
# 빈칸이면 그 다음도 감시 가능한지 알아본다
change(nx, ny, d, g)
# 최종적으로 출력할 결과 값
ans = n * m + 1
# cctv의 index를 변경시켜 가며 g를 바꿔나감
def dfs(index, g):
global ans, n, m
# 만약 cctv를 전부다 고려했다면 사각지대의 갯수를 센 다음 ans를 업데이트한다
if index == len(cctv):
cnt = 0
for i in range(n):
for j in range(m):
if g[i][j] == 0:
cnt += 1
if cnt < ans:
ans = cnt
return ans
# cctv 의 타입별로 , 90도 회전하며 방향 조합 별로 탐색
cctvtype, x, y = cctv[index]
# cctv 타입 별로 가능한 조합
for arrows in rotate[cctvtype-1]:
# 이 전의 그래프를 deepcopy해둠 -> 방향 별로 g가 달라질거니까
tmp_g = copy.deepcopy(g)
for arrow in arrows:
change(x, y, arrow, tmp_g)
# 방향별로 감시 가능 영역을 다 -1로 표시함
# 인덱스 늘려서 dfs해서 다음 cctv에 대한 감시 가능 영역을 표시한다
dfs(index+1, tmp_g)
dfs(0, g)
print(ans)return 값을 고쳤다
재귀로 감시 가능한 칸을 바꿔주는 것도 잘 나오는 구현
+) dfs 재귀...
^^~