DFS & BFS 이해하기

DFS : 깊이 우선 탐색

• 그래프 전체를 탐색하는 방법 중 하나.
• 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법.
• 스택이나 재귀함수를 사용하여 구현(코딩테스트에서는 보통 재귀를 사용)

재귀함수로 사용하여도 시스템 스택에 쌓이게 되므로 스택이라고 생각할 수 있다.

 

1. 시작 정점의 한 방향으로 갈 수 있는 곳 까지 깊이 탐색한다.(가면서 지나가는 것들을 하나씩 담는다)
2. 가다가 더 이상 갈 곳이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다.
3. 다른 방향의 정점으로 탐색을 계속 반복하며 결국 모든 정점을 방문한다.
4. 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야하므로 후입 선출 구조의 스택을 사용한다.

 

알고리즘

1. 시작 점점 v를 결정하여 방문한다. => 방문한 곳은 방문했다고 체크를 해야 함.
2. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다.
3. w를 v로 하여 다시 2를 반복한다.
   • 여기서 주의! v에서 방문 한 곳이 있을 떄만 push를 하는 것이고 v에서 방문 할 곳이 없다면 push없이 되돌아간다
4. 방문하지 않은 정점이 없다면, 탐색 방향을 바꾸기 위해 pop하여 마지막 방문 점점을 v로 하여 2를 반복한다.
5. 스택이 공백이 될 때 까지 2를 반복한다.

즉, 되돌아 오기 위해 사용한 자료구조로 스택을 사용했다는 것을 기억해야한다.

 

 

 

BFS : 너비 우선 탐색

• 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘
• 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결
• 미로를 빠져나가는 최단 거리를 구하는 문데에서 효과적

가까운 노드부터 우선적으로 탐색한다는 점에서 선입선출 방식의 큐(queue) 자료구조를 활용, 즉 BFS는 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에 꺼내도록 알고리즘을 작성한다.

 

알고리즘

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복