[알고리즘] DFS (깊이 우선 탐색)

개념 그래프 : 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 비선형 자료구조 위와 같이 그래프는 연결된 객체 간의 관계를 표현하는 자료구조이며, 방향 그래프와 무방향 그래프로 나눌 수 있다. 이러한 그래프를 탐색할 때 사용하는 방법 중 하나가 DFS (Depth-First Search), 깊이 우선 탐색이다.

이 외에도 다익스트라, 플로이드 와샬, BFS가 있다. 이미지와 같이 노드 1을 시작으로 차례대로 노트 9까지 순회한다.

위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있다. 즉 DFS란, 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 해당 노드의 자식들을 모두 탐색한 후 다른 형제 노..........