728x90
728x90
깊이 우선 탐색 ( Depth-First Search )
루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
특징
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;
}
}
}
}
}
728x90
300x250
