깊이 우선 탐색(dfs)

dfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32https://hongcode.tistory.com/32를 참고 하자.

깊이 우선 탐색(dfs)

DFS(Depth First Search) 이름 뜻 그대로 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색하는 방법을 말한다.

장점

• 최선의 경우, 가장 빠른 알고리즘이다. 운이 좋게 항상 해에 도달하는 올바를 경로를 선택하다면, dfs가 최소 실행시간에 해를 찾는다.
• bfs에 비해 저장공간의 필요성이 적다. 백트레킹을 해야 하는 노드들만 저장해주면 된다.

단점

• 찾은 해가 최적이 아닐 가능성이 있다.(알고리즘은 항상 최악의경우를 생각해야 함)
• 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 달하는데 가장 오랜 시간이 걸린다.

예를 들어보자!!

먼저 정점을 하나 선택한다. 선택된 정점의 인접란 정점 중에 아직 방문하지 않은 정점 중 하나를 선택해 방문한다. 위에서 설명했듯이 깊이 우선 탐색이므로 0에 인접한 1에 방문하였다면 그다음엔 1에 인접한 정점들이 우선적으로 탐색 되게 된다. 그래프를 보면서 알아보자. 빨간색은 현재 방문한 노드이고 초록색은 방문했던 노드입니다.

맨 처음 방문한 0번 노드의 인접한 노드는 1, 2번이다. 이 중에서 더 작은 번호의 1번 노드를 방문했다(인접 리스트에 저장된 순서대로 방문). 이다음에는 2번이 아니라 1번에 인접하고 있는 0, 3, 5번 노드 중 하나를 방문할 건데, 0은 이미 방문을 했으므로 3, 5번 중에 방문하게 된다.

더 작은 번호인 3을 방문하였다. 마찬가지로 3번에 인접한 노드는 1, 4이고 1은 방문했었으므로 4를 방문할 것이다.

5번 노드를 방문할 수밖에 없다.

 

5번 노드에선 더 이상 방문하지 않은 인접한 노드가 없다. 그러면 4번 노드로 돌아가서 4번 노드의 인접한 노드들 중 아직 방문하지 않은 정점을 찾아 방문해야 한다. 4번에도 없으면 3번, 없으면 1번... 이렇게 확인하면서 돌아가서 0번 노드까지 오게 된다.

 

0번 노드에 인접한 노드들 중에 아직 방문하지 않은 2번 노드가 있으므로 방문한다.

똑같은 방식으로 진행한다.

마찬가지..

8번 노드를 방문하게 되면 아무리 다시 돌아가도 더 이상 방문할 노드가 남지 않게 된다. 그래프 전체를 탐색한 것이다.

어떠한 정점에서 더 이상 방문할 노드가 없을 까 자신을 불렀던 정점으로 되돌아가는 것은 어떻게 구현을 할 수 있을까. 두 가지 방법이 있다.

첫 번째는 스택이다. https://hongcode.tistory.com/28 방문하는 순서대로 노드를 스택에 쌓고, 방문이 끝나면 스택에서 pop 해주고 꼭대기 값에 인접한 방문하지 않은 노드가 있는지 확인하는 방식으로 구현이 가능하다.

두 번째는 재귀 함수이다. 재귀 함수 또한 스택 메모리 공간에 쌓아 올려지는 구조를 띄기 때문에 재귀 함수를 사용해도 이것을 구련 할 수 있다. 주로 이 방법을 사용한다. 코드를 통해서 보자.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool visited[10]; // 노드 방문시 방문 여부를 검사하기위한 배열
vetor<int> adj[10]; // 인접리스트(벡터)를 이용해서 그래프 만들기
void dfs(int now){
	visited[now]=1;
	for(nt i=0; i<adj[now].size(); i++){
		int next = adj[now][i];
		if(!visited[next])dfs(next);
	}
}

dfs의 시간 복잡도

O(V+E)

정점과 간선의 개수 합이다. 한 번 방문한 노드는 다시 방문하지 않으며, 한 노드에서 다음으로 방문할 노드들을 순회하는 횟수가 그 노드의 차수와 같기 때문이다.

만약 인접 리스트가 아니라 인접 행렬로 그래프를 구성하게 된다면 다음에 방문할 정점을 찾을 때 모든 정점을 순회하며 둘이 이어져 있는지를 체크해야 하므로 O(V^2)이다. 경우에 따라서 시간 차이가 크게 나게 된다.

관련 문제

• BOJ 11724 연결 요소의 개수 <https://www.acmicpc.net/problem/11724>
• BOJ 1012 유기농배추 <https://www.acmicpc.net/problem/1012>
• BOJ 1743 음식물 피하기 <https://www.acmicpc.net/problem/1743>
• BOJ 2667 단지번호붙이기 <https://www.acmicpc.net/problem/2667>
• BOJ 2583 영역구하기 <https://www.acmicpc.net/problem/2583>
• BOJ 10026 적록색약 <https://www.acmicpc.net/problem/10026>
• BOJ 11403 경로 찾기 <https://www.acmicpc.net/problem/11403>
• BOJ 2468 안전 영역 <https://www.acmicpc.net/problem/2468>
• BOJ 10552 DOM <https://www.acmicpc.net/problem/10552>
• BOJ 9466 텀 프로젝트 <https://www.acmicpc.net/problem/9466>
• BOJ 10265 MT <https://www.acmicpc.net/problem/10265>