BFS와의 차이점이 궁금합니다.(64번)

Question

안녕하세요.

64번 해당문제에서 DFS로 설명해주셨습니다.

이진트리로 DFS와 BFS를 각각 비교하면 깊이탐색, 너비탐색이 이해가 금방되는데, 이렇게 방향그래프에서 DFS와 BFS의 차이점을 잘 모르겠습니다. 해당 문제에서는 1->5로 가는 방법으로

1 2 3 4 5

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5 이 순서인데,

이걸 BFS방식으로 풀면 혹시

1 2 5

1 4 5

1 3 4 5

1 4 2 5

1 2 3 4 5

1 3 4 2 5 순으로 찾게되나요?

감사합니다.

Answer

큐를 이용해 BFS로 탐색하면 탐색순서는 1번 정점에서 1개의 간선으로 갈 수있는 곳 다 방문하고, 그 다음 간선 두 번만에 가는 곳 다 방문하는 식이니 경로의 간선수가 적은 것부터 완성한다고 생각하시면 됩니다.

위에 순서는 BFS로 탐색하는 순서가 맞습니다.

Answer

안녕하세요^^

BFS는 출발점에서 특정 정점으로 가는 최단거리를 구하는데 쓰는 알고리즘입니다.

출발점에서 특정 정점으로 가는 모든 경우(모든 경로)의 수를 구할 때는 DFS를 씁니다.

즉 어떤 경우의 수를 구할 때 DFS로 하고, 특정 최단거리 또는 최소 횟수를 구할 때 BFS라고 생각하시면 됩니다.