BFS(Breadth-First Search)
BFS(Breadth-First Search) 너비 우선 탐색. 이름 그대로 그래프에서 넓은 부분을 우선적으로 탐색하는 알고리즘을 말한다. BFS의 탐색 순서 BFS는 A에서 출발해서 A에서 인접한 노드인 B, C부터 우선적으로 모두 탐색한다. 그 다음 B, C에서 인접한 노드인 D, E, F, G. 그 다음 F, G는 마지막 노드이니, D, E에서 인접한 노드인 H, I, J를 하나씩 탐색하면 모든 노드의 탐색이 끝나게 된다. 이때, 각 단계의 노드들은 그 안에서 방문 순서가 바뀔 수는 있지만, 다른 단계의 노드와는 방문 순서가 바뀔 수 없다. 여기서 가장 처음 시작하는 0단계 노드에서 K단계 노드까지는 최단거리가 K가 된다. 최단거리는 즉, A에서 마지막 노드까지 가는 데 필요한 간선의 최소 개수와 ..
2023. 5. 19.
DFS(Depth-First Search)
DFS(Depth-First Search) 깊이 우선 탐색. 이름 그대로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 말한다. 정확하게는 DFS는 깊은 부분을 끝까지 탐색하다가, 막히면 다시 돌아와서, 다른 부분을 깊게 탐색한다. DFS의 탐색 순서 DFS는 A에서 출발해서 B를 선택하여 탐색을 시작하고, B에서 이미 A는 탐색했으니, D로 넘어간다. 그리고 D에서는 이미 B를 탐색했으니, H로 넘어가게 되고, 이제 더 이상 방문할 인접 노드가 없는 H에서는 자신의 앞전 노드인 D로 돌아가고, 방문할 수 있는 노드인 I로 이동한다. 그리고 I는 거꾸로 D로 돌아가고, 이제 더 이상 방문할 노드가 없으니, B로, 그 다음은 A로 거슬러 올라간다. 그리고 A에서는 이제 반대편 노드를 탐색하기 시작하..
2023. 5. 19.
