[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)

 

 

깊이 우선 탐색 (DFS, Depth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 

 

깊이 우선 탐색은 간단하게 "한쪽 방향으로 파고들어 탐색하는 방식"으로 미로에서 길을 찾는 것과 같다. 

시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

 

장점

• 현 경로상의 노드만 저장하면 되기 때문에 그래프 높이 만큼의 저장공간을 필요로 한다.
  즉, 최대저장공간의 수요가 비교적 적다.
• 목표가 위한 깊이가 깊을 경우 해를 빠르게 구할 수 있다. 

 

단점

• 해가 없는 경로에 깊이 빠질 수 있다. 
• 목표에 이르는 경로가 다수인 경우, 목표에 닿으면 팀색을 끝내기 때문에 최적의 해가 아닐 수 있다.

주로 모든 경로를 탐색해야하거나, 경로 탐색에 조건이 있는 경우 사용한다.

(조건에 따라 가지치기를 하는 방법을 백트래킹이라고 한다.)

 

주의할 점은 반드시 방문 체크가 필요하다.

부모 - 자식간의 관계로 이루어지는 트리에서는 상관없지만, 

순환을 갖는 그래프에서 방문 체크를 하지 않으면 무한 루프에 빠지게 된다. 

 

 

그림으로 이해하면 쉽기 때문에, 아래 그림의 트리와 그래프를 예시로 탐색 순서를 알아보자! 

 

 

위 그림과 같은 트리가 있을 때 DFS 탐색 순서는  A  - B - D - H - I - E - C - F - G - J 

부모를 탐색한 후에 한쪽 방향으로 계속 탐색하기 때문에 순서가 전위순회와 같다.

 

 

위 그림과 같은 방향 그래프에서는  A - B - G - C - E - F - D  가 된다.

방문 체크를 하지 않을 경우 E를 방문한 후에 A를 다시 방문하면서 루프에 빠지게 된다. 주의!

 

 

구현 방법

구현 방법에는 스택과 재귀를 이용한 두가지 방법이 있다.

 

재귀 호출을 이용한 방법

트리라면 루트 노드, 그래프라면 임의의 정점에서 시작한다.

1. 현재 방문한 정점에 방문처리를 한다.

2. 방문하지 않았고, 이웃한 정점으로 이동한다.

public static void dfs(int node) {
	visit[node] = true;
	System.out.print(node+" ");
		
	for (int next = 0; next < V; next++) {
		if (visit[next] == false && graph[node][next] == 1)
			dfs(next);
	}
}

 

스택을 이용한 방법

트리라면 루트 노드, 그래프라면 임의의 정점을 스택에 삽입한다.

1. 스택에서 pop한 정점이 방문하지 않았다면, 방문처리를 한다. 
   이미 방문한 정점이라면 넘어간다.

2. 방문하지 않았고, 이웃한 정점을 스택에 삽입한다. 
    순서가 중요할 경우 이웃한 정점을 확인할 때 거꾸로 확인해야한다.

public static void dfs(int node) {
	stack.push(node);

	while(!stack.empty()) {
		int curr = stack.pop();

		if (!visit[curr]) {
			visit[curr] = true;
			System.out.print(curr+" ");
				
			//스택이라서 거꾸로 돌린다
			for (int next = V-1; next >= 0; next--) {
				if (!visit[next] && graph[curr][next] == 1)
					stack.push(next);
			}
		}
	}
}

 

 

DFS를 활용한 문제

[백준] 1260번: DFS와 BFS

[백준] 1937번: 욕심쟁이 판다

[백준] 1520번: 내리막 길