0x00 DFS
DFS( Depth First Search)
: 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘
방문여부확인을 스택을이용한다
BFS( Breadth First Search)
: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
방문여부확인을 큐를이용한다
0x01 예시
0x02 BFS vs DFS
DFS는 한 방향으로 막힐때 까지 쭉 직진을 하는것처럼 보인다.
BFS, DFS 모두 순회하면서 체크하는 알고리즘이긴 하나 BFS에서 유용하게 썻던 "현재 보는 칸으로부터 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없다.
결국 앞으로 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만 짜게 된다.
앞으로 트리나 그래프 자료구조를 배울 때 DFS가 필요하다.
'공부 일지 > 알고리즘' 카테고리의 다른 글
[바킹독의 알고리즘] 0x0C강 - 백트래킹 (1) | 2024.01.08 |
---|---|
[바킹독 알고리즘]0x0B강 - 재귀 (0) | 2024.01.08 |
[배열]BOJ 1475번 - 방 번호 (0) | 2023.12.30 |
[배열]BOJ 2577번 - 숫자의 개수 (0) | 2023.12.30 |
[기초 코드 작성 요령 II]BOJ 15552번 - 빠른 A+B (0) | 2023.12.30 |