DFS와 재귀함수
def recursive_function(i):
# 7번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 7:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
'''
출력결과
1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다.
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다.
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다.
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다.
5 번째 재귀함수에서 6 번째 재귀함수를 호출합니다.
6 번째 재귀함수에서 7 번째 재귀함수를 호출합니다.
6 번째 재귀함수를 종료합니다.
5 번째 재귀함수를 종료합니다.
4 번째 재귀함수를 종료합니다.
3 번째 재귀함수를 종료합니다.
2 번째 재귀함수를 종료합니다.
1 번째 재귀함수를 종료합니다.
'''
우선순위로 예를 들자면 첫 번째 재귀가 실행되고 그 안에서 두 번째 재귀가 실행된다면 첫 번째 재귀는 잠시 대기상태가 됩니다. 그리고 두 번째 재귀의 내용을 실행하다 종료가 된다면 이어서 첫 번째 재귀의 내용을 실행합니다.
본 예시에서 두 번째 재귀함수가 종료된다음 차례로 첫 번째 재귀함수를 종료하는것을 볼 수 있습니다.
# DFS 함수 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
위코드의 dfs작동원리에 대해서 쉽게 풀이해서 정리합니다.
dfs(graph, 1, visited) 첫 번째 함수호출.
visited[1] = true > 출력 1 > graph[1]에 2가 false라서 dfs(graph, 2, visited) 첫 번째 재귀실행.
visited[2] = true > 출력 2 > graph[2]에 7이 false라서 dfs(graph, 7, visited) 두 번째 재귀실행.
visited[7] = true > 출력 7 > graph[7]에 6이 false라서 dfs(graph, 6, visited) 세 번째 재귀실행.
visited[6] = true > 출력 6 > graph[6]에 7이 true라서 세 번째 재귀종료.
graph[7]에 8이 false라 dfs(graph, 8, visited) 네 번째 재귀실행. (두 번째 재귀 내용을 이어서)
visited[8] = true > 출력 8 > graph[8]에 1, 7이 true라서 두 번째 재귀종료, 네 번째 재귀종료.
graph[1]에 3이 false라 dfs(graph, 3, visited) 다섯 번째 재귀실행. (첫 번째 재귀 내용을 이어서)
visited[3] = true > 출력 3 > graph[3]에 4가 false라서 dfs(graph, 4, visited) 여섯 번째 재귀실행.
visited[4] = true > 출력 4 > graph[4]에 5가 false라서 dfs(graph, 5, visited) 일곱 번째 재귀실행.
visited[5] = true > 출력 5 > graph[5]에 3, 4가 true라서 첫 번째, 다섯 번째, 여섯 번째, 일곱 번째, 재귀종료.
첫 번째 함수종료.
출력 결과 : 1 2 7 6 8 3 4 5
정리해서 써봐도 상당히 복잡하네요.
그냥 간단하게 함수호출 1 > 2 7 6 > 세 번째 재귀종료 > 8 > 두 번째 재귀종료 > 3 4 5 > 첫 번째 재귀종료 > 함수종료 라고 보면 될것 같습니다.
(dfs&재귀함수에 대해 자세히 정리된 링크)
https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=832