알고리즘 기초 - 경로 탐색 알고리즘

너비 우선 탐색(Breadth-First Search, BFS)

그래프를 탐색하는 알고리즘이다. 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드를 광범위하게 탐색한다. 두 노드 사이에 경로가 있는지 확인하고 그 사이의 최단 경로를 결정한다.

너비 우선 탐색 알고리즘은 기본적으로 0층에서 시작하며 다음 층으로 이동하기 전에 해당 층의 모든 노드를 방문할 때까지 수평으로 이동한다.

즉, 한 번 거친 노드 순서를 저장한 후 다시 꺼내는 선입선출 원칙으로 탐색한다. 주로 큐를 이용해 구현한다.

 

루트 노드 1에서 시작하여 값이 7인 노드에 도달하려고 하는 경우, 1에서 가장 가까운 2, 3을 탐색한다.

그 다음 2에서 가장 가까운 4, 5, 6, 7을 탐색하여 7에 도달한다.

 

깊이 우선 탐색(Depth-First Search, DFS)

그래프를 탐색하는 알고리즘이다. 시작 노드와 직접 연관된 하위 노드의 끝까지 모두 탐색한 후 다음 하위 노드를 탐색하는 방법이다.

 

너비 우선 탐색이 같은 층의 노드를 모두 탐색한 후 다음 층을 탐색한다면, 깊이 우선 탐색은 일단 경로 하나의 모든 층을 탐색한 후 그 다음에 다른 경로의 모든 층을 탐색한다.

따라서 깊이 우선 탐색을 구현할 때는 보통 재귀 호출이나 스택을 명시하는 방법을 사용한다.

 

백트래킹

모든 경우를 다 탐색해 문제의 해답을 찾는 제어 알고리즘.

어떤 규칙으로 정해진 해답을 찾지 못하면 다시 처음으로 돌아와 다른 규칙으로 문제의 해답을 찾는다.

보통 트리 데이터 구조에서는 깊이 우선 탐색과 너비 우선 탐색을 이용해 백트래킹을 실행한다.