깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS) -> 스택 사용 (재귀 이용 -> 재귀 자체가 스택임)

루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

특징

• 깊이 우선 탐색(DFS) 에 비해서 너비 우선 탐색(BFS)이 보다 좀 더 간단하다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.

과정

결국 이동 순서는
0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0
다음과 같다.

시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)