넓이 우선 탐색
[image] 최선 우선 탐색(Best First Search)에 대한 내용은 최선 우선 탐색 문서를 참조하십시오.
Breadth First Search. 흔히 줄여서 BFS로 쓴다.
한국어 표기는 넓이 우선 탐색[1] 또는 너비 우선 탐색.
'''넓이 우선 탐색'''은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다.
[image]
깊이 우선 탐색과, 넓이 우선 탐색의 차이점을 보여준다. 왼쪽이 깊이 우선 탐색, 오른쪽이 너비 우선 탐색이다.
흔히 너비 우선 탐색으로도 쓰인다.
DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.
전 세계의 모든 사람들의 관계를 그래프로 만들고, 'Jack' 과 'Kongnamoo' 의 관계를 잇는 간선을 찾는다고 가정해보자.
BFS를 사용하면 Jack에게 관련된 간선들을 하나씩 파악해나가기 때문에 Kongnamoo를 비교적 빠르게 찾을 수 있지만, DFS로 파악할 경우 Jack의 자식노드를 모두 파악하고 가므로 Jack의 부모님, Jack의 외할머니...Jack의 외할머니의 친구의친구.. 등으로 무한한 길이로 빠져 영원히 종료하지 못하는 것이다. 때문에 DFS 에서는 너무 깊게 뻗어나가는 것을 막기 위해 때때로 limit를 걸어두는 것이다.
또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 '''가중치가 없는 그래프[3][4]에서는'''' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다.
BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 자료 구조 Queue를 사용하는 경우가 일반적이다. 배열에서 사용하는 경우, 방향 데이터를 이용해 배열의 시작점에서 범위를 넓혀 가면서 탐색하는 것이다.
1. 개요
Breadth First Search. 흔히 줄여서 BFS로 쓴다.
한국어 표기는 넓이 우선 탐색[1] 또는 너비 우선 탐색.
'''넓이 우선 탐색'''은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다.
- 루트에서 시작한다.
- 자식 노드들을 [1]에 저장한다.[2]
- [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
- [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
- 위의 과정을 반복한다.
- 모든 노드를 방문하면 탐색을 마친다.
[image]
깊이 우선 탐색과, 넓이 우선 탐색의 차이점을 보여준다. 왼쪽이 깊이 우선 탐색, 오른쪽이 너비 우선 탐색이다.
흔히 너비 우선 탐색으로도 쓰인다.
2. 특징
DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.
전 세계의 모든 사람들의 관계를 그래프로 만들고, 'Jack' 과 'Kongnamoo' 의 관계를 잇는 간선을 찾는다고 가정해보자.
BFS를 사용하면 Jack에게 관련된 간선들을 하나씩 파악해나가기 때문에 Kongnamoo를 비교적 빠르게 찾을 수 있지만, DFS로 파악할 경우 Jack의 자식노드를 모두 파악하고 가므로 Jack의 부모님, Jack의 외할머니...Jack의 외할머니의 친구의친구.. 등으로 무한한 길이로 빠져 영원히 종료하지 못하는 것이다. 때문에 DFS 에서는 너무 깊게 뻗어나가는 것을 막기 위해 때때로 limit를 걸어두는 것이다.
또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 '''가중치가 없는 그래프[3][4]에서는'''' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다.
3. 소스 코드로의 구현
BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 자료 구조 Queue를 사용하는 경우가 일반적이다. 배열에서 사용하는 경우, 방향 데이터를 이용해 배열의 시작점에서 범위를 넓혀 가면서 탐색하는 것이다.
4. 같이보기
[1] 사실 이 의미로 쓰인 넓이는 틀린 표현이다. 넓이가 '''가로 길이와 세로 길이를 곱한''' 2차원 측도이기 때문.[2] 정확히는 자식의 위치.[3] 모든 간선에서 주는 가중치가 같다는 뜻이다. 여기에 예시로 나온건 가중치가 안 써있으니 가중치가 없고, 보통 선에 숫자가 쓰여있으면 그게 가중치다.[4] 가중치가 있는 그래프에서 최단경로 찾기는 다익스트라 알고리즘 참고.