dfs #파이썬 #자료구조 #알고리즘 #그래프 #재귀함수 #recursive #dfs_recursive #node #append #graph #인접노드 #노드 #그래프 #자식노드 #인접리스트
-
파이썬 자료구조 알고리즘, DFS -> 재귀함수로 구현Python 2024. 7. 21. 20:55
DFS Depth First Search 깊이 우선 탐색 이라는 뜻으로, 아래와 같이 노드가 갈 수 있는 깊이만큼 계속 가다가 길이 없으면 다시 백해서 다른 방향을 탐색해서 가는 구조를 말한다. DFS를 구현하는 방법은 재귀함수로 구현하는 방법과 스택으로 구현하는 방법 두가지가 있는데 재귀함수로 코드를 짤 때, 가장 중요한 포인트는 두가지이다. 1. 반복적으로 발생하는 일이 뭔지 아는 것2. 종료 조건을 아는 것각각의 숫자는 노드 노드 1을 방문하고 2, 5, 9 차례대로 방문할거다. 근데 2에 방문 했는데 2한테 자식이 있으니까 5한테 가기 전에 2의 자식인 3한테 가고 3의 자식인 4한테 갔다가 더이상 자식이 없음을 확인 후 백해서 2로 온 후 다른 자식이 있는지 확인하고 없으면 5한테 가는 순이다..