[알고리즘] 깊이 우선 탐색(DFS)

깊이 우선 탐색 ( Depth-First Search )

---

루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

출처 : http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

특징

1. 모든 노드를 방문하고자 하는 경우에 사용한다.

2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다.

3. 검색이 아닌 순회를 할 경우 많이 사용한다.

공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 

 

장점

1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.

2. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

1. 해가 없는 경로에 깊이 빠질 수 있다.

2. 경로가 다수일 경우 DFS는 해에 다다르면 탐색을 끝내기 때문에, 이 때 얻어진 해는 최적이 아닐수도 있다.

 

 

 

재귀 형태로 DFS 구현

---

public class DFS_Recursion {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		dfs(1);
	}
	
	static void dfs(int nodeIndex) {
		// 방문 처리
		vistied[nodeIndex] = true;
		
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				dfs(node);
			}
		}
	}
}

 

Stack으로 DFS 구현

---

import java.util.Stack;

public class DFS_stack {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	// DFS 사용 할 스택
	static Stack<Integer> stack = new Stack<>();
	
	public static void main(String[] args) {
		
		// 시작 노드를 스택에 넣어줍니다.
		stack.push(1);
		// 시작 노드 방문처리
		vistied[1] = true;
		
		// 스택이 비어있지 않으면 계속 반복
		while(!stack.isEmpty()) {
			
			// 스택에서 하나를 꺼냅니다.
			int nodeIndex = stack.pop();
			
			// 방문 노드 출력
			System.out.print(nodeIndex + " -> ");
			
			// 꺼낸 노드와 인접한 노드 찾기
			for (int LinkedNode : graph[nodeIndex]) {
				// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리 
				if(!vistied[LinkedNode]) {
					stack.push(LinkedNode);
					vistied[LinkedNode] = true;
				}
			}
		}
	}
}

 

 

https://namu.wiki/jump/lx6xBC2GBl7zL0GkVf2iAdDWvdnMIa0h5yJwIUhAw3FZ8mmo%2BeBWdrG5FG4xZXsLCJ4ANQjocKfQajOsZqXirchQWd4udqKXzK2UEdewNnW1dhS1I%2BejXYRwtb8aSO4z

https://codingnojam.tistory.com/44