[알고리즘] DFS 스택 구현 VS 재귀 구현

DFS는 스택으로 구현 하는 방법, 재귀로 구현하는 방법 두 가지가 있다.

전자는 BFS의 구현 코드에서 큐를 스택으로만 바꾸면 되고,
재귀의 경우는 방문처리만 잘 해주면 된다.

그런데, 스택으로 구현하는 경우, DFS의 탐색 순서를 체계적으로 만드는 것이 어렵다.
https://www.acmicpc.net/problem/1260
해당 백준 문제가 그렇다.

일반적인 DFS 문제라면 대부분 인접 노드 중 탐색 방향에 딱히 제한이 없으나,
해당 문제는 번호가 작은 노드부터 접근하라는 제한이 들어간다.

이 때는, 작은노드를 접했을 때 다시 해당 노드를 시작점으로 하여 dfs를 호출하는게 좋다.

결론

stack으로 DFS구현시, 탐색 순서의 보장이 어렵다.
=> 재귀는 탐색 순서를 그나마 보장 가능함