바이러스 백준 2606 dfs 종료는 어떻게 되는건가요?
def dfs(idx):
global visited, graph, answer
visited[idx] = True
answer += 1
for i in range(1,N+1):
if not visited[i] and graph[idx][i]:
dfs(i)이와 같은 dfs 재귀함수에서 dfs(1)이 맨 처음에 실행되고 조건에 따라 계속 재귀되는데 마지막 dfs(7)까지 간다고 했을 때 range(1,N+1)에 범위는 넘지만 dfs(8), dfs(9), ... 이런식으로 계속 코드가 돌아버릴 수도 있는 것이 아닌가요??
DFS와 재귀함수가 처음이여서 질문을 명확하게 못 작성한 것 같네요.
return이라는게 필요한 것이 아닌지, 재귀함수에 종료조건이 어떻게 되는 것인지 궁금해서 여쭤봅니다.
답변 기다리겠습니다. 감사합니다
답변 1
1
녜힁님 안녕하세요 :)
제가 7,8,9 라는 숫자가 어떻게 나온건지는 약간 헷갈리지만 이렇게 정리해볼게요. N = 7 이었다면 반복문이 1~7까지만 반복하기 때문에 8, 9를 호출할 일은 없을 것 같아요.
만약 N = 10인데 연결된 노드가 7번까지만 있다면, 실제 반복문은 10까지 돌겠지만 graph의 값이 false 여서 호출이 되지 않을 겁니다.
여기서 10번까지 전부 연결이 되어있더라도 한번 방문한 뒤에는 visited[i] = true 가 되기 때문에 재방문은 방지되고요.
그래서 첫째는 반복문을 활용해서 1부터 N 포함까지만 호출하기 때문에 무한 재귀호출을 막고 있고, 한번 호출된 노드가 또 호출되지 않도록 visited로 두번 막고 있다고 이해하면 될것 같아요!
혹시 제 설명이 부족했거나 제가 질문을 잘못 이해했다면 댓글 남겨주세요! 오늘도 공부하느라 고생 많으셨습니다 :D
itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)
1
34
1
백준 13565 침투 질문
1
93
2
침투/섬개수 질문
1
138
2
재귀함수 질문
1
145
1
백준 1260 (DFS 와 BFS) 프린트 위치 질문
1
122
1
촌수계산(백준 2644) 질문
1
187
2
다른 주제 강의
1
138
2
graph
1
197
1
재귀 함수 Depth
1
181
1
백준 DFS
1
217
1
[바닥장식][런타임에러] 질문 있습니다.
1
292
3
그래프 짤 때 adjacency matrix vs adjacency list
1
393
2
2644문제(촌수 구하기) 질문입니다.
1
252
2
DFS 문제 하나 여쭤봅니다!..
1
297
1
다음강의
1
245
1
알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문
1
285
1
1260 문제 풀이에서는 함수 global로 변수 선언
2
212
1
PyPy3와 Python3
1
332
1
백준 2606
1
216
1
22479번 문제 런타임 에러 도와주세요 ㅠㅠ
1
439
1
11724 문제 질문
1
305
2
그래프 초기화
1
282
1
선생님! 바이러스 문제 코드 질문있어요오
1
276
2
질문있습니다!
1
332
1