Notice
Recent Posts
Recent Comments
Link
코딩 공부
[Python](DFS) 백준 15683번 : 감시 본문
728x90

<접근 방법>
모든 경우를 고려해야하므로 "백트래킹"을 이용하겠다. 또한, dfs에서 n이 진행될수록 카피본을 넘겨줘야하므로 deepcopy를 이용해보겠다.
- cctv 타입별 가능한 방향 dictionary를 만들어놓아야겠다.
- cctv의 x, y좌표와 타입을 하나의 튜플로 묶어 정보를 저장해두어야겠다.
- dfs를 이용해 cctv를 순서대로 돌리면서 그 cctv가 가능한 방향을 순회하면서 감시영역으로 체크하고 다음 cctv로 넘기는 로직을 짜야겠다.
- 마지막으로 cctv개수만큼 n이 깊어졌다면, answer를 사각지대 최소 개수로 갱신한다.
<어려웠던 점>
- deepcopy를 어느 부분에서 사용해야할지 혼동되어 디버깅할 때 엉뚱하게 중복되어 감시되기도 했다.
- cctv_info의 타입1의 정보를 "1:[0, 1, 2, 3]"과 같이 설정했었는데 그럴 경우, int타입의 순회가 불가능하므로
"TypeError : 'int' object is not iterable"이라는 오류가 뜨게 된다.

from copy import deepcopy
def dfs(n, arr):
global answer
if n == len(cctv): # cctv를 모두 돌았다면
# 사각지대 개수 카운트
cnt = 0
for i in range(N):
for j in range(M):
if arr[i][j] == 0:
cnt += 1
answer = min(answer, cnt) # 사각지대 최소 개수로 정답 갱신
return
i, j, num = cctv[n] # 현재 cctv의 x좌표, y좌표, 타입
for temp in cctv_info[num]: # 타입별 가능한 방향 순회
t_arr = deepcopy(arr)
for k in temp: # 가능한 방향으로 감시
ci, cj = i, j
while True:
ni = ci + directions[k][0]
nj = cj + directions[k][1]
if not(0<=ni<N and 0<=nj<M) or t_arr[ni][nj] == 6: # 범위 밖이거나 벽을 만나면 break
break
t_arr[ni][nj] = '#'
ci, cj = ni, nj
dfs(n+1, t_arr)
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
cctv_info = {1:[[0], [1], [2], [3]], 2:[(0, 2), (1, 3)], 3:[(0, 1), (1, 2), (2, 3), (3, 0)], 4:[(0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1)], 5:[(0, 1, 2, 3)]}
directions = {0:(-1, 0), 1:(0, 1), 2:(1, 0), 3:(0, -1)}
answer = N*M
cctv = []
for i in range(N):
for j in range(M):
if 0<arr[i][j]<6: # 1~5일 경우 cctv이므로 cctv 리스트에 정보 추가
cctv.append((i, j, arr[i][j]))
dfs(0, arr)
print(answer)

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.
728x90
'삼성 SW 역량 테스트 기출 문제' 카테고리의 다른 글
[Python](시뮬) 백준 17144번 : 미세먼지 안녕! (0) | 2024.03.04 |
---|---|
[Python](BFS) 백준 16234번 : 인구 이동 (0) | 2024.03.01 |
[Python](BFS&DFS / BFS&Itertools) 백준 14502번 : 연구소 (2가지 방법) (2) | 2024.02.05 |
[Python](DFS) 백준 14500번 : 테트로미노(2가지 방법) (0) | 2024.02.04 |
[Python](시뮬) 백준 14499번 : 주사위 굴리기 (2) | 2024.02.03 |