[Algorithm] 깊이 우선 탐색(DFS, Depth First Search)

개요

 

◎ 깊이 우선 탐색이란?

◎ 사용 목적

◎ 그림 예시

◎ 구현 코드 - 인접 행렬 (Java)

◎ 구현 코드 - 인접 리스트 (Java)

◎ 시간 복잡도

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 깊이 우선 탐색(DFS)에 대해 적어보는 시간을 가져보려고 합니다.

 

 

깊이 우선 탐색이란?

 

깊이 우선 탐색이란 그래프 탐색 기법 중 하나로 한 번 탐색을 시작한 정점의 최대 깊이까지 탐색을 한 뒤 같은 높이에 있는 다른 정점을 탐색하는 기법입니다.

 

그래프 탐색에 대해서도 설명을 드리자면 한 정점을 시작으로 다른 존재하는 모든 정점을 한 번씩 방문하는 탐색을 그래프 탐색이라고 합니다.

 

 

사용 목적

 

깊이 우선 탐색을 사용하는 목적은 모든 정점을 탐색하여 원하는 값이 존재하는지 찾기 위해 사용합니다.

 

대표적인 예는 미로 탈출이 있습니다.

 

한 번 탐색을 시작한 방향으로 더 이상 길이 없을 때까지 가고 막 다른 길에 도달하면 이전의 장소로 돌아와 가지 않았던 방향으로 다시 더 이상 길이 없을 때까지 가며 탈출 장소를 찾는 것입니다.

 

그리고 이처럼 갈수 있는 모든 경로를 전부 찾는 것을 완전 탐색(Exhaustive Search)이라 하고 자식 노드에서 부모 노드로 되돌아와 다른 동작을 진행하는 것을 백트래킹(BackTracking)이라고 부릅니다.

 

 

그림 예시

 

 

다음 그림과 같은 그래프가 존재할 때 0번 정점으로부터 시작하여 깊이 우선 탐색을 할 경우 다음과 같은 결과가 나옵니다.

 

 

간단히 설명을 하자면 다음과 같습니다.

 

1-1. 0번 정점에서 갈 수 있는 정점은 1번, 3번이 있습니다.

1-2. 1번 정점은 아직 방문하지 않았기 때문에 1번 정점을 방문합니다.

 

2-1. 1번 정점에서 갈 수 있는 정점은 0번, 2번, 5번이 있습니다.

2-2. 0번 정점은 이미 방문했기 때문에 방문하지 않습니다.

2-3. 2번 정점은 아직 방문하지 않았기 때문에 2번 정점을 방문합니다.

 

3-1. 2번 정점에서 갈 수 있는 정점은 1번이 있습니다.

3-2. 1번 정점은 이미 방문했기 때문에 방문하지 않습니다.

3-3. 2번 정점에서 더 이상 방문할 수 있는 정점이 존재하지 않기 때문에 상위 요소인 1번 정점으로 되돌아 갑니다.

 

4-1. 1번 정점에서 2번 정점 이후로 갈 수 있는 정점은 5번이 있습니다.

4-2. 5번 정점은 아직 방문하지 않았기 때문에 5번 정점을 방문합니다.

 

.

.

.

 

이와 같은 결과를 만들어주는 코드도 작성해보겠습니다.

 

728x90

 

구현 코드 - 인접 행렬 (Java)

 

package graph;

public class DepthFirstSearchArray {
	public static void main(String[] args) {
		int N = 7; // 정점의 갯수
		boolean[][] graph = new boolean[N][N]; // true면 길(간선)이 존재, false면 길(간선)이 없음
		
		addEdge(graph, 0, 1);
		addEdge(graph, 0, 3);
		addEdge(graph, 1, 2);
		addEdge(graph, 1, 5);
		addEdge(graph, 5, 6);
		addEdge(graph, 3, 4);
		
		boolean visited[] = new boolean[N]; // 정점의 방문 여부 / true면 방문, false면 미 방문
		
		System.out.print("방문 순서: ");
		DFS(graph, visited, 0); // 방문 순서: 0 1 2 5 6 3 4 
	}
	
	public static void DFS(boolean[][] graph, boolean[] visited, int index) {
		if(visited[index]) { // 이미 방문한 index라면 되돌아가기
			return;
		}
		
		System.out.print(index + " ");
		
		visited[index] = true; // 방문 체크
		
		for(int i=0; i<visited.length; i++) {
			if(!visited[i] && graph[i][index]) { // 아직 방문하지 않고 길(간선)이 존재할 경우
				DFS(graph, visited, i);
			}
		}
	}
	
	public static void addEdge(boolean[][] graph, int u, int v) { // 길(간선) 추가
		graph[u][v] = graph[v][u] = true;
	}
}

 

 

구현 코드 - 인접 리스트 (Java)

 

package graph;

import java.util.ArrayList;
import java.util.List;

public class DepthFirstSearchList {
	public static void main(String[] args) {
		int N = 7; // 정점의 갯수
		List<Integer> graph[] = new List[N];
		
		for(int i=0; i<graph.length; i++) { // 초기화
			graph[i] = new ArrayList<Integer>();
		}
		
		addEdge(graph, 0, 1);
		addEdge(graph, 0, 3);
		addEdge(graph, 1, 2);
		addEdge(graph, 1, 5);
		addEdge(graph, 5, 6);
		addEdge(graph, 3, 4);
		
		boolean visited[] = new boolean[N]; // 정점의 방문 여부 / true면 방문, false면 미 방문
		
		System.out.print("방문 순서: ");
		DFS(graph, visited, 0); // 방문 순서: 0 1 2 5 6 3 4 
	}
	
	public static void DFS(List<Integer> graph[], boolean[] visited, int index) {
		if(visited[index]) { // 이미 방문한 index라면 되돌아가기
			return;
		}
		
		System.out.print(index + " ");
		
		visited[index] = true; // 방문 체크
		
		for(int i=0; i<graph[index].size(); i++) { // 존재하는 길 탐색
			int nextIndex = graph[index].get(i);
			
			if(!visited[nextIndex]) { // 아직 방문하지 않을 경우
				DFS(graph, visited, nextIndex);
			}
		}
	}
	
	public static void addEdge(List<Integer> graph[], int u, int v) { // 길(간선) 추가
		graph[u].add(v);
		graph[v].add(u);
	}
}

 

 

시간 복잡도

 

인접 행렬의 시간 복잡도는 O(N^2)입니다.

 

위의 코드를 예시로 들어보겠습니다.

 

index가 0인 DFS 메서드를 시작으로 N번 만큼의 for문이 실행되고 for문의 i값이 1일 때 다시 DFS 메서드를 실행시킵니다.

 

다시 실행된 DFS 메서드는 N만큼의 for문이 다시 실행되고 for문의 i값이 2일 때 다시 DFS 메서드를 실행시킵니다.

 

이것이 반복되어 index가 N-1이 될때까지 DFS 메서드가 실행되며 총 N번만큼 DFS 메서드를 호출합니다.

 

결과적으로 N만큼의 for문을 실행시키는 DFS 메서드를 N번 호출하기 때문에 N x N = N^2이라는 값이 나오게 됩니다.

 

인접 리스트의 시간 복잡도는 O(E)입니다.

 

여기서 E는 길(간선)의 개수를 의미합니다.

 

인접 리스트도 위의 코드로 예시를 들면 index가 0인 DFS 메서드를 시작으로 index에 연결되어 있는 간선의 개수만큼 for문이 실행되며 다시 DFS 메서드를 실행시킵니다.

 

인접 행렬과 동일하게 DFS 메서드를 총 N번만큼 호출하며 for문을 통해 연결되어 있는 간선만큼 실행되기 때문에 간선을 모두 합한 E만큼의 시간이 사용됩니다.

 

참고적으로 위의 코드에서 E값은 연결된 선이 6개이지만 양방향으로 연결되어 있어 6 x 2 = 12라는 값이 나옵니다.

 

또한 모든 정점에 모든 간선이 존재하면 개수는 N^2 - N입니다. (자기 자신에게 가는 경우 제외)

 

그리고 이 값은 E와 동일하기 때문에 N^2 - N ≥ E라는 값이 만들어지고 O(N^2) ≥ O(N+E)라는 식이 성립됩니다.

 

 

정리

 

● 깊이 우선 탐색이란 시작 정점의 최대 깊이까지 탐색한 뒤 다른 정점을 탐색하는 기법

● 구현 방법은 인접 행렬, 인접 리스트 2가지가 존재

● 인접 행렬의 시간 복잡도는 O(N^2), 인접 리스트의 시간 복잡도는 O(E)

● 인접 리스트보다는 인접 행렬이 더 명시적이어서 코드 이해와 구현이 쉬운 편

 

이상으로 깊이 우선 탐색(DFS)에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.