DFS(깊이 우선 탐색, Depth-First Search)는 그래프나 트리를 탐색하는 알고리즘 중 하나이다. 이 방법은 주어진 그래프의 모든 정점(Vertex)을 방문하는 경로를 찾을 때 사용한다.
DFS는 이름에서 알 수 있듯이, 깊이 방향으로 우선 탐색하는 것을 기본 원리로 한다. 즉, 시작 노드에서 가능한 한 깊숙히 들어가면서 노드를 탐색하고, 더 이상 탐색할 자식 노드가 없을 경우 이전 노드로 돌아와서 그 다음 노드를 탐색하는 방식이다.
DFS의 동작 과정은 다음과 같다:
- 시작 노드를 선택하여 방문하고 방문한 노드를 스택에 push한다.
- 현재 방문한 노드에 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면 그 노드를 방문하고 방문한 노드를 스택에 push한다. 만약 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 pop한다.
- 더 이상 2번의 과정을 반복할 수 없을 때까지 계속 반복한다.
DFS는 스택 또는 재귀 호출을 이용하여 구현할 수 있으며, 그래프의 모든 노드를 방문하고 싶을 때, 경로 탐색을 해야할 때 주로 사용된다.
import java.util.*;
class Graph {
private int numOfNodes; // 노드의 수를 저장
private LinkedList<Integer> adjListArray[]; // 인접 리스트 배열
// 생성자
Graph(int numOfNodes) {
this.numOfNodes = numOfNodes; // 노드의 수 설정
// 배열의 크기를 노드의 수로 설정
adjListArray = new LinkedList[numOfNodes];
// 각 노드마다 인접 노드를 저장할 리스트 생성
for (int i = 0; i < numOfNodes; i++) {
adjListArray[i] = new LinkedList<>();
}
}
// 무방향 그래프에 간선 추가
void addEdge(int src, int dest) {
// src에서 dest로의 간선 추가
adjListArray[src].add(dest);
// dest에서 src로의 간선 추가
adjListArray[dest].add(src);
}
// 노드 u에서 시작하는 그래프의 DFS를 실행하는 함수
void DFSUtil(int node, boolean[] visited) {
// 현재 노드를 방문했다고 표시하고 노드 출력
visited[node] = true;
System.out.print(node + " ");
// 이 정점과 인접한 모든 정점에 대해 재귀적으로 탐색
Iterator<Integer> iterator = adjListArray[node].listIterator();
while (iterator.hasNext()) {
int n = iterator.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
// DFS 순회를 수행하는 함수. 재귀적인 DFSUtil()을 사용함.
void DFS(int startNode) {
// 모든 정점을 방문하지 않았다고 표시
boolean[] visited = new boolean[numOfNodes];
// 재귀적 도우미 함수를 호출하여 모든 정점에서 DFS 순회를 출력
DFSUtil(startNode, visited);
}
}
public class Main {
public static void main(String args[]) {
Graph graph = new Graph(5); // 5개의 노드를 가진 그래프 생성
graph.addEdge(0, 1); // 노드 0과 1 사이에 간선 추가
graph.addEdge(0, 4); // 노드 0과 4 사이에 간선 추가
graph.addEdge(1, 2); // 노드 1과 2 사이에 간선 추가
graph.addEdge(1, 3); // 노드 1과 3 사이에 간선 추가
graph.addEdge(1, 4); // 노드 1과 4 사이에 간선 추가
graph.addEdge(2, 3); // 노드 2와 3 사이에 간선 추가
graph.addEdge(3, 4); // 노드 3과 4 사이에 간선 추가
System.out.println("DFS traversal of the graph starting from node 0: ");
graph.DFS(0); // 노드 0에서 시작하는 그래프의 DFS 순회 시작
}
}
DFS는 그래프의 모든 노드를 방문하는 알고리즘 중 하나로, 현재 정점에서 가능한 한 깊숙이 들어가서 노드를 방문한 후, 더 이상 방문할 노드가 없을 때 이전 노드로 돌아가 다음 노드를 방문하는 방식을 취한다. 이러한 방식은 스택의 LIFO(Last In First Out) 원칙을 따르는데, 이는 재귀 함수의 호출 스택으로 쉽게 구현할 수 있다.
위 코드에서는 Graph 클래스 내에 DFSUtil 메소드를 통해 실제 DFS 알고리즘이 구현되어 있다. DFSUtil 메소드는 인접 노드를 찾아서 아직 방문하지 않은 노드를 재귀적으로 탐색한다. DFS 메소드에서는 방문 여부를 저장하는 boolean 배열 **visited**를 초기화하고 시작 노드를 지정하여 DFS를 시작한다.
이 예제에서 그래프는 다음과 같이 구성된다.
0
/ \\
1---4
| \\ |
| \\|
2---3
그래프에 대해 DFS 함수를 호출하면 노드 **0**에서 시작하는 DFS 탐색 결과를 콘솔에 출력하게 됩니다. 출력된 결과는 DFS 탐색 순서에 따른 노드 번호이다.
예를 들어, 아래와 같은 그래프가 있다고 가정하면
A
/ \\
B---C
| \\ |
| \\|
D---E
이 그래프에 DFS를 적용한다면 다음과 같은 순서로 노드를 방문하게 된다.
- 먼저 시작 노드인 **A**를 방문한다. (방문 노드: A)
- **A**에 인접한 노드 중 하나인 B를 방문한다. (A -> B)
- 다음으로 **B**에 인접한 노드 중 하나인 C를 방문한다. (A -> B -> C)
- **C**에 인접한 노드 중 **A**와 **B**는 이미 방문한 상태이므로 E를 방문한다.(A -> B -> C -> E)
- **E**에 인접한 노드 중 **B**와 **C**는 이미 방문했으므로 D를 방문한다. (A -> B -> C -> E -> D)
- 모든 노드를 방문했으므로 탐색을 종료한다.
위와 같이 깊이를 우선적으로 탐색하게 되면, 처음 시작 노드에서 가장 멀리 있는 노드를 먼저 방문하게 된다. DFS는 이와 같은 특성 때문에 미로 찾기, 경로 탐색 등에서 많이 활용된다.
왜... \을 쓰면 \\로 기록될까요....ㅠㅠㅠ
'CS > 알고리즘' 카테고리의 다른 글
| 동적 계산법 (0) | 2023.06.07 |
|---|---|
| 큐(Queue) (0) | 2023.06.07 |
| 스택(Stack) (0) | 2023.06.07 |
| 이진 검색 트리(Binary Search Tree, BST) (0) | 2023.05.30 |
| 해싱(Hashing) (0) | 2023.05.30 |
