인프런 커뮤니티 질문&답변
작성한 질문수
BFS와의 차이점이 궁금합니다.(64번)
작성
·
297
0
안녕하세요.
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 순으로 찾게되나요?
감사합니다.
답변 2
0
김태원
지식공유자
큐를 이용해 BFS로 탐색하면 탐색순서는 1번 정점에서 1개의 간선으로 갈 수있는 곳 다 방문하고, 그 다음 간선 두 번만에 가는 곳 다 방문하는 식이니 경로의 간선수가 적은 것부터 완성한다고 생각하시면 됩니다.
위에 순서는 BFS로 탐색하는 순서가 맞습니다.
0
김태원
지식공유자
안녕하세요^^
BFS는 출발점에서 특정 정점으로 가는 최단거리를 구하는데 쓰는 알고리즘입니다.
출발점에서 특정 정점으로 가는 모든 경우(모든 경로)의 수를 구할 때는 DFS를 씁니다.
즉 어떤 경우의 수를 구할 때 DFS로 하고, 특정 최단거리 또는 최소 횟수를 구할 때 BFS라고 생각하시면 됩니다.
감사합니다. 혹시 그럼
[[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 순으로 찾게되나요?]] 라고 질문 드렸던 부분은 틀린 것인가요?