그래프 탐색 문제는 대부분 BFS, DFS를 둘 다 사용할 수 있다.
하지만 그럼에도 불구하고 상황에 따라 효율적인 알고리즘이 있다.
BFS - 최단 경로
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
가중치가 1인 최단 경로를 구할 때는 BFS가 효율적이다.
DFS로 최단 경로를 구하면 그래프가 아닌 트리라는 확증이 있어야 한다.
아니면 내가 최종적으로 방문한 경로가 최단 경로인지 확신할 수 없기 때문이다.
반면 BFS는 도착 정점에 도달하는 순간이 최단경로이다.
최단거리 문제 알고리즘에 대한 궁금증 정리
DFS, BFS와 다익스트라 알고리즘에 대한 여러가지 의문점
sigridjin.medium.com
DFS - 백트래킹
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
백트래킹 알고리즘과 DFS는 차이가 있지만 백트래킹은 DFS에서 조건문을 걸어
모든 경로를 탐색하는 DFS 방식이 아닌 해가 아닌 것 같으면 다시 되돌아가서 탐색한다고 생각하면 된다.
N-Queen은 한줄씩 퀸을 놓을 자리를 탐색하고 퀸을 놓아도 되는 조건에서만
재귀를 통해 다음 줄로 내려가 퀸을 놓을 자리를 계속 탐색한다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] 동적 계획법(DP) - 조합 (0) | 2023.02.22 |
|---|---|
| [알고리즘] 벨만 포드 알고리즘 (0) | 2023.02.20 |
| [알고리즘] 그래프와 트리 (트리는 방향 그래프인가?) (0) | 2023.02.09 |
| [알고리즘] 최소 스패닝 트리 - 프림(Prim) 알고리즘 (0) | 2023.02.08 |
| [알고리즘] 플로이드 와샬 알고리즘 (0) | 2023.02.07 |
