DFS

" 탐색을 할 때 깊이를 우선으로 탐색하는 알고리즘 "

---

장점

현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.

---

단점

1. 해가 없는 경로를 탐색 할 경우에도 단계가 끝날 때까지 탐색 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용하기도 한다.

2. DFS는 해에 도착하면 탐색을 종료하기 때문에 DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다.

---

과정

한 경로로 탐색 하다 특정 상황에서 최대한 깊숙하게 들어가서 확인 후 다시 돌아가 다른 경로로 탐색하는 방식

---

활용

1. 백트랙킹
2. 단절선 찾기 및 단절점 찾기
3. 위상정렬
4. 사이클 찾기

---

슈도 코드

DFS(u)

for each neighbor v of u

  if v is unvisited, tree edge, DFS(v)

  else if v is explored, bidirectional/back edge

  else if v is visited, forward/cross edge

구현 코드 (recursion & stack)

#include<bits/stdc++.h>
#define MAX 100000
using namespace std;

int n, m, s;
bool visit[MAX];
vector<int> adj[MAX];
stack<int> st;

void dfs_r(int v) {
	visit[v] = true;
	printf("%d", v);

	for (int i = 0; i < adj[v].size(); i++) {	// 인접 노드 재귀함수 호출
		int nxt = adj[v][i];
		if (!visit[nxt]) {
			dfs_r(nxt);
		}
	}
}

void dfs_st(int v) {
	visit[v] = true;
	st.push(v);	// 루트 노드 삽입

	while (!st.empty()) {
		int cur = st.top();
		st.pop();
		printf("%d", cur);
		// 숫자 작은 노드 먼저 방문하기 위함
		for (int i = adj[cur].size() - 1; i >= 0; i--) {
			int nxt = adj[cur][i];
			if (!visit[nxt]) {
				st.push(nxt);
				visit[nxt] = true;
			}
		}
	}
}

int main() {
	scanf_s("%d %d %d", &n, &m, &s);	// 노드 수, 간선 수, 시작 노드

	for (int i = 0; i < m; i++) {
		int s, e;
		scanf_s("%d %d", &s, &e);
		adj[s].push_back(e);
		adj[e].push_back(s);
	}
	for (int i = 0; i < 1001; i++) {
		sort(adj[i].begin(), adj[i].end());
	}

	memset(visit, 0, sizeof(visit));
	dfs_r(s);
	printf("\n");

	memset(visit, 0, sizeof(visit));
	dfs_st(s);

	return 0;
}

---

참조 사이트
https://sweetday-alice.tistory.com/176