[C++/코테] DFS

DFS

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

과정

BFS와 동일한데, 큐가 스택으로 바뀐다.

1. 시작하는 칸에 스택을 넣고 방문했다는 표시를 남긴다.
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다.
3. 해당 칸에 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다.
4. 스택이 빌 때까지 2번을 반복한다.

모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.

구현

BFS에서 구현했던 코드를 참고한다. 스택으로만 바꾸면 됨.

2023.11.13 - [Algorithm] - [C++/코테] BFS

[C++/코테] BFS

BFS vs. DFS

• BFS는 거리 순으로 방문
• BFS의 큰 특징이었던, "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다."는 성질이 DFS에서는 성립하지 않는다. 즉 거리 계산에는 DFS를 사용할 수 없다. 
• 다차원 배열에서 순회하는 문제를 풀 때는 BFS만 사용. 그래프와 트리 자료구조에서는 DFS가 필요하다.

---

출처: https://youtu.be/93jy2yUYfVE?si=Xsook6cagJyQTHGv