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

설명

Depth First Search(깊이우선탐색)으로, 루트에서 시작해서 해당 분기를 최대한 깊숙히 탐색 후 다음 분기로 넘어가는 알고리즘이다.

백트래킹*에 사용된다.

주로, 재귀호출, 스택으로 구현한다.

*백트래킹 : 조건을 만족하는 모든 조합의 수를 찾아보는 것으로, 가지치기를 통해 가도 되지 않은 루트는 고려하지 않고 탐색하는 기법

DFS 예시

Q. 0,1,2,3,4가 이렇게 연결되어 있다면 DFS에 따른 방문 순서를 구하라

(1) 0과 연결된 1,2,4 중 제일 작은 1에 방문함
→ [0, 1]

(2) 1과 연결된 0,2 중 방문하지 않은 2를 방문함
→ [0,1,2]

(3) 2와 연결된 0,1,3 중 방문하지 않은 3을 방문함
→ [0,1,2,3]

(4) 3과 연결된 2,4 중 방문하지 않은 4를 방문함
→ [0,1,2,3,4]

(5) 3으로 backtracking, 2로 backtracking ...

구현 코드

재귀+인접행렬

boolean[] visited = new boolean[100];
int[][] graph = new int[100][100]; 
//graph[x][y] == 1 이면, x와 y가 연결되어 있음

void DFS(int v) {
	visited[v] = true;
	System.out.print(v+" ");

	for(int i=1; i<graph[v].length; i++) {
		if(graph[v][i] == 1 && !visited[i])
			dfs(i);
	}
}

재귀+인접리스트

LinkedList<Integer>[] adjList = new LinkedList[100];
// 이미 모두 연결된 상태라고 가정
boolean[] visited = new boolean[100];
void DFS(int v) {
	visited[v] = true;
	System.out.print(v+" ");

	Iterator<Integer> iter = adjList[v].listIterator();
	while(iter.hasNext()){
		int w = iter.next();
		if(!visited[w])
			dfs(w);
	}
}

스택

boolean[] visited = new boolean[100];
int[][] graph = new int[100][100]; 
//graph[x][y] == 1 이면, x와 y가 연결되어 있음

void DFS(int start){
	Stack<Integer> stack = new Stack<Integer>();
	stack.push(start);
	
	while(!stack.isEmpty()){
		int v = stack.pop();
		if(!visited[v]){
			visited[v] = true;
			System.out.println(v+" ");
			for(int i=0; i<graph[v].length; i++){
				if(!visited[i])
					stack.push(i);
			}
		}
	}
}

시간 복잡도

인접리스트 : O(V+E)
인접행렬 : O($V^2$)

단점

• 단순 검색 속도는 BFS 보다 느림
• 정답을 구하면 탐색이 종료되므로, 최단 경로를 보장하지 않음

장점

• 현재 분기의 노드만 기억하면 되므로, 저장 공간이 비교적 적음
• 구현이 BFS보다 간단함