-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
바이러스 백준 2606 dfs 종료는 어떻게 되는건가요?
23.10.06 16:14 작성 조회수 94
1
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
개발자로 취직하기
지식공유자2023.10.06
녜힁님 안녕하세요 :)
제가 7,8,9 라는 숫자가 어떻게 나온건지는 약간 헷갈리지만 이렇게 정리해볼게요. N = 7 이었다면 반복문이 1~7까지만 반복하기 때문에 8, 9를 호출할 일은 없을 것 같아요.
만약 N = 10인데 연결된 노드가 7번까지만 있다면, 실제 반복문은 10까지 돌겠지만 graph의 값이 false 여서 호출이 되지 않을 겁니다.
여기서 10번까지 전부 연결이 되어있더라도 한번 방문한 뒤에는 visited[i] = true 가 되기 때문에 재방문은 방지되고요.
그래서 첫째는 반복문을 활용해서 1부터 N 포함까지만 호출하기 때문에 무한 재귀호출을 막고 있고, 한번 호출된 노드가 또 호출되지 않도록 visited로 두번 막고 있다고 이해하면 될것 같아요!
혹시 제 설명이 부족했거나 제가 질문을 잘못 이해했다면 댓글 남겨주세요! 오늘도 공부하느라 고생 많으셨습니다 :D
답변 1