이 글은 혼자 공부하면서 적어간 내용이기에 평어체로 작성되었고 틀린 내용이 있을 수 있습니다.
이 점 양해부탁드리며 틀린 내용 지적, 질문은 언제든 환영합니다!서론
그래프 자료구조의 완전 탐색 알고리즘에는 DFS와 BFS가 있다. DFS(Depth-First Search)는 깊이 우선 탐색, BFS(Breadth-First Search)는 너비 우선 탐색으로 이는 탐색 순서에 따라 구분된다. 이 두가지 알고리즘을 이용하기 위해서는 스택과 큐, 그리고 그래프 자료구조에 대해서 이해하고 있어야 한다.
이번 포스팅에서는 DFS에 대해서 알아보도록 하겠다.
깊이우선탐색 (DFS)
Depth-First Search, 깊이 우선 탐색은 루트 노드에서 시작하여 다른 분기(branch)로 넘어가기 전, 현재 탐색하고 있는 분기의 끝까지 다 탐색한 후에 다음 분기로 넘어가는 방식이다. 즉, 현재 분기의 가장 깊은 곳까지 탐색한 다음 넘어가므로 '깊이 우선'이다.
동작 순서
- 루트 노드를 스택에
삽입(push)하고 방문처리 한다. - 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문처리 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.pop - 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
👉 방문처리를 해주는 이유?
방문처리를 해주지 않으면 이미 방문했던 노드를 다시 스택에 넣는 과정을 반복함으로써 무한루프에 빠질 수 있기 때문!
사용
DFS는 주로 스택 또는 재귀 함수를 이용하여 구현한다.
DFS를 사용하는 것이 좋은 문제 유형들
- 그래프의 모든 정점을 방문하는 것이 주요한 문제
이는 DFS와 BFS 중 어느 것을 사용하여도 큰 문제는 없다. - 경로의 특징을 저장해둬야 하는 문제
탐색하는데 있어 같은 숫자를 2번 지나가면 안되는 조건과 같이 경로마다 특징을 저장해둬야 할 때에는 DFS를 사용해야 한다. - 탐색 대상 그래프가 정말 큰 경우
백트래킹 (Backtracking)
해를 찾아가는 도중, 현재의 경로가 해가 되지 않을 것 같다고 판단될 때, 더이상 현재 경로로 가지 않고 되돌아가는 방법이다.
백트래킹은 주로 DFS를 사용하며, 재귀함수에 조건문을 걸어 답이 되지 않는 경우에 return하여 다른 경우를 탐색할 수 있도록 한다.
예시
백준 15649번 문제의 재귀함수 부분, 즉 깊이우선탐색을 하는 부분만 가져와보았다.
예를 들어 n=4, m=4일때, 1234를 다 채워서 출력하고 나면 2341 이런 식으로 구하는 것이 아니라 return을 하면서 1243, 1324 ... 이런 식으로 뒤에서부터(=가장 깊은 곳부터) 채워나가는 방식이다.
void recur(int k)
{
if(k==m) { // 배열을 다 채웠을 때 출력 후 리턴
for(int i=0; i<m; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for(int i=1; i<=n; i++) { // 각 탐색단계마다 1부터 n까지 수를 검사
if(!checked[i]) { // 이미 방문한 수가 아니라면
arr[k]=i; // 출력하기 위한 배열에 추가
checked[i] = true; // 방문표시
recur(k+1); // 다음번째 수를 탐색하러
checked[i] = false; // 출력한 뒤이므로 방문해제
} // 모든 수가 방문상태라면 if문 안이 실행되지 않으므로 return됨
}
}참고문헌
https://hudi.blog/dfs-bfs/
https://chanhuiseok.github.io/posts/algo-23/
https://velog.io/@lucky-korma/DFS-BFS의-설명-차이점
