안녕하세요 오늘은 DFS에 대해 알아보겠습니다. DFS는 Depth First Search의 약자이며, 깊이 우선 탐색이라고 부릅니다. 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후 돌아와 다른 노드로 탐색하는 방식입니다. Stack을 사용하여 데이터를 탐색합니다.
1. DFS (Depth First Search)의 장점과 단점
깊이 우선 탐색은 최대한 깊이 내려간 후 더 이상 깊이 갈 곳이 없으면 옆으로 이동합니다. 예를 들어, 미로 찾기에서는 최대한 한 방향으로 직진합니다. 더 이상 길이 없으면 Stack을 pop 하며 길을 찾아갑니다.
● 장점
현 경로상의 노드들만 기억하면 되므로 저장 공간 수요가 비교적 적습니다.
목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다.
● 단점
해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸릴 수 있습니다.
얻어진 해가 최단 경로가 된다는 보장이 없습니다.
따라서 최단 경로를 찾고 싶다면 BFS(Breadth First Search)를 사용해야 합니다.
2. DFS의 흐름
DFS의 대표적인 그림입니다. 각 노드는 정점(Vertex)를 표현하는 것이고, 선은 간선(Edge)이며 각 정점을 연결합니다.
만약 시작 정점이 1번일 경우, DFS는 숫자가 낮은 부분부터 우선 탐색을 합니다. 설계를 하는 사람에 따라 다르지만, 일반적으로는 숫자가 낮은 정점부터 탐색을 합니다.
1번에서 2번을 탐색합니다. 그다음은 시작점이 2번이 되고 4번과 5번이 있는데 숫자가 더 낮은 4번으로 갑니다. 그리고 8번으로 이동을 합니다. 8번이 다시 시작점이 되며, 4번은 이미 방문을 하여 넘어가고 5번으로 갑니다. 5번을 탐색하면 2번과 8번이 인접한 정점이 되는데, 둘 다 이미 탐색을 하였으므로 8로 다시 도착하여 6번으로 갑니다. 6번에서는 방문하지 않은 3번으로 갑니다. 마지막으로 3번에서는 방문하지 않은 7번으로 갑니다. 모든 정점을 탐색하였으므로 DFS는 종료됩니다.
정리를 하면, 1 → 2 → 4 → 8 → 5 → (8) → 6 → 3 → 7이 됩니다.
8번은 다시 돌아왔으므로 괄호로 표시를 했습니다. 하지만 8번은 다시 탐색하는 의미는 아닙니다.
3. Stack을 활용한 DFS 예제
① static 이너 클래스 사용
import java.util.*;
public class DfsExam {
static class Graph {
int vertex;
LinkedList<Integer> list[];
public Graph(int vertex) {
this.vertex = vertex;
list = new LinkedList[vertex];
for (int i = 0; i < vertex; i++) {
list[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination) {
list[source].addFirst(destination);
list[destination].addFirst(source);
}static inner class를 사용하여 구현하였습니다. vertex는 그래프의 정점의 개수를 나타내고, list는 인접 리스트를 사용하여 그래프의 간선 정보를 저장합니다. Graph 생성자에는 정점을 매개 변수로 받습니다. 인접 리스트를 초기화하고, 연결된 노드들의 리스트를 저장합니다. addEdge 메서드는 그래프에 새로운 edge를 추가하는 메서드입니다.
② DFS 함수
public void DFS(int start) {
System.out.print("방문 순서 : ");
boolean[] visited = new boolean[vertex];
Stack<Integer> stack = new Stack<Integer>();
stack.push(start);
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
System.out.print(v + " ");
visited[v] = true;
for (int i = 0; i < list[v].size(); i++) {
int dest = list[v].get(i);
if (!visited[dest])
stack.push(dest);
}
}
}
}DFS 알고리즘을 이용하여 그래프의 노드를 방문하는 함수를 구현했습니다. boolean[] visited는 그래프의 각 노드를 방문했는지를 나타내는 배열입니다. 처음에는 모두 false로 초기화됩니다. Stack<Integer> stack는 DFS를 위한 Stack 구조입니다. 탐색하고자 하는 노드를 임시로 저장하기 위해 사용합니다.
③ printGraph() 메서드
public void printGraph() {
for (int i = 0; i < vertex; i++) {
LinkedList<Integer> nodeList = list[i];
if (nodeList.isEmpty() == false) {
System.out.print(i + "번 정점이" + "연결되어 있는 정점은 : ");
for (int j = 0; j < nodeList.size(); j++) {
System.out.print(" " + nodeList.get(j));
}
}
System.out.println();
}
}
}printGraph 메서드는 반복문을 사용하여 그래프의 각 정점을 순회합니다. list[i]를 통해 정점 i와 연결된 인접 정점들의 리스트를 가져옵니다. 만약 해당 정점과 연결된 인접 정점들이 있다면, 해당 정보를 출력합니다.
④ main 함수
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
graph.addEdge(2, 3);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(4, 5);
graph.printGraph();
graph.DFS(0);
}
}Graph 클래스를 사용하여 그래프를 생성하고, 그래프의 각 정점과 연결된 인접 정점들을 출력한 뒤에 DFS 알고리즘을 사용하여 그래프를 탐색합니다. addEgde 메서드는 간선을 추가합니다.
4. 실행 결과
실행이 정상적으로 되는 것을 확인할 수 있습니다.
