dfs
1) 특정한 타겟으로 잡은 노드로부터 가장 멀리 있는 노드를 먼저 탐색함.
2) 노드 전체를 탐색하기 때문에, 백트래킹에 사용됨.
3) 방문 불변수로 true, false로 사용함.
bfs
1) 모든 노드에서 동일한 가중치로 탐색할 때 사용함.
2) 최단거리 알고리즘
3) 한 번 방문한 노드는 더 이상 방문 안함.
-
가중치가 다를 경우에는 다익스트라, 벨만 포드를 사용해야 함.
: 백준 2번 책에 30번 챕터 설명 있음. -
최단 거리를 구해야 할 때는 bfs로 풀자
bfs는 주변에 연결된 친구들을 방문하는 방식이므로 운이 좋아 바로 주변에 있으면 빠르게 찾아낸다. -
모든 정점을 방문할 필요는 없다. : bfs
-
모든 정점을 방문해야 할때는 dfs로 풀자.
dfs는 주변의 한 친구만 잡아서 드립다 그 친구 한테만 들어가므로, 주변에
발견하고자 하는 정점이 있더라고 다음에 찾게 되므로, 최단거리에는 적합하지 않다.
물로 찾을 수는 있지만, bfs가 적합하다는 것이다. -
포함 + 포함되지 않음을 나타낼때, 즉 집합을 만들때는 dfs를 사용하자.
🔥🔥🔥