BFS-1
DFS 나 BFS 나 임의의 정점에서 시작하여 모든 정점을 방문한다. 라는 목적은 같다. 이것만이 목적이라면 어떤 것을 택해도 좋다.
하지만, BFS 만이 특별히 이용되는 경우가 있는데, 모든 가중치가 1일 때, 최단 거리를 구하는 알고리즘일 때 이다.
(만약, 가중치가 1이 아니라면 다익스트라 알고리즘 을 사용한다.)
단, 가중치와 비용은 같아야 한다.
BFS-2
제한 조건에 따라서, 정점을 나누어서 생각해야할 수 있다. 아래의 이모티콘 문제를 보면, 제한 조건이 다르기 때문에 정점을 나눠서 구현했다. 여기서는, 정점을 "이차원으로 만듦"으로써 나누었다.
반응형
'알고리즘 & 코딩 테스트 > code.plus' 카테고리의 다른 글
| [알고리즘 중급 1/3] 분할 정복 (이분 탐색 / 병합 정렬(merge sort) / 퀵 정렬(quick sort) (0) | 2021.10.09 |
|---|---|
| [기초] 시뮬레이션 (0) | 2021.10.04 |
| [기초] 그래프의 탐색 (0) | 2021.10.02 |
| [기초] 그래프 (0) | 2021.09.25 |
| [기초] 큐 (0) | 2021.09.25 |
