[알고리즘] 넓이 우선 탐색 (BFS)
오늘은 넓이 우선탐색에 대해 알아보겠습니다. 넓이 우선탐색은 거리를 기준으로 하는 탐색 방법이라 할 수 있습니다. 즉, 시작점으로부터 거리가 같은 노드를 먼저 탐색하는 방법입니다. 아래 그래프를 기준으로 설명하겠습니다. 거리가 동일할 때는 작은 숫자부터 탐색한다고 가정하면 시작점이 0일때 BFS 방식을 사용하면, 0->1->4->2->3 순서로 그래프를 탐색하게 됩니다. 0과 인접한 1과 4를 먼저 탐색하게 됩니다. 0과 인접한 것은 이제 없기 때문에 1과 인접한 것 중 이전에 탐색하지 않았던 노드인 2와 3을 탐색하게 됩니다. 1과 인접한 것은 이제 없고 4와 인접한 것 중 이전에 탐색하지 않았던 노드는 없기 때문에 탐색을 종료합니다. 위의 그래프를 인접 행렬 방식으로 나타내면 다음과 같습니다. 탐색한..
알고리즘
2021. 12. 27. 17:27
