코딩테스트의 많은 문제들은 그래프 또는 트리 구조를 기반으로 하고 있습니다. 이러한 문제를 해결하는 데 유용한 알고리즘 중 하나가 깊이 우선 탐색(Depth-First Search, DFS)입니다. 이번 강좌에서는 DFS의 개념과 자바로 구현하는 방법을 알아보겠습니다.
1. 깊이 우선 탐색(DFS)란?
깊이 우선 탐색은 그래프 탐색 알고리즘의 일종으로, 가능한 한 깊이 들어가면서 노드를 탐색하는 방법입니다. 즉, 한 갈래로 계속 나아가다가 더 이상 진행할 수 없게 되면 한 단계 앞의 노드로 되돌아가서 다른 갈래를 탐색하는 방식입니다.
2. DFS의 특징
- 스택을 사용하여 방문한 노드를 저장합니다.
- 재귀(recursion)를 통해 구현될 수 있습니다.
- 너비 우선 탐색(BFS)과는 달리 노드의 깊이나 경로를 우선 고려합니다.
3. 문제 정의
다음과 같은 그래프가 있다고 가정해 봅시다:
A
/ \
B C
/ \ \
D E F
이 그래프에서 DFS를 사용하여 A에서 시작해 D까지의 경로를 찾아보려 합니다. 경로를 찾고 A에서 D까지 방문한 노드를 출력하는 것이 목표입니다.
4. 문제 해결 과정
DFS를 사용하여 문제를 해결하기 위해, 먼저 그래프를 표현한 후 DFS 알고리즘을 구현해야 합니다.
4.1 그래프 표현
그래프는 보통 인접 리스트나 인접 행렬로 표현할 수 있습니다. 여기서는 인접 리스트를 사용하여 그래프를 표현하겠습니다.
자바로 그래프 구현하기
import java.util.*;
class Graph {
private Map> adjacencyList;
public Graph() {
adjacencyList = new HashMap<>();
}
public void addEdge(String source, String destination) {
adjacencyList.putIfAbsent(source, new ArrayList<>());
adjacencyList.get(source).add(destination);
}
public Map> getAdjacencyList() {
return adjacencyList;
}
}
4.2 DFS 알고리즘 구현
DFS 알고리즘은 다음과 같은 방식으로 구현될 수 있습니다. 방문한 노드를 저장하기 위해 Set을 사용하고 재귀 호출을 통해 깊이 탐색을 수행합니다.
자바 DFS 메서드
class DFS {
private Set visited;
private List path;
public DFS() {
visited = new HashSet<>();
path = new ArrayList<>();
}
public void depthFirstSearch(Graph graph, String node) {
if (!visited.contains(node)) {
visited.add(node);
path.add(node);
for (String neighbor : graph.getAdjacencyList().get(node)) {
depthFirstSearch(graph, neighbor);
}
}
}
public List getPath() {
return path;
}
}
5. 전체 코드
이제 전체 코드를 하나로 합쳐서 사용해 보겠습니다. 다음은 그래프를 만들고 DFS를 실행하는 전체 코드입니다.
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
DFS dfs = new DFS();
dfs.depthFirstSearch(graph, "A");
System.out.println("DFS 경로: " + dfs.getPath());
}
}
6. 코드 실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:
DFS 경로: [A, B, D, E, C, F]
결과에서 보듯이 DFS는 A에서 시작하여 B를 방문하고 그 후 D로 깊이 들어갔습니다. DFS의 탐색 순서가 유지되는 것을 확인할 수 있습니다.
7. 심화 학습
이 강좌에서는 DFS의 개념과 기본적인 구현 방법을 소개했습니다. 더 나아가 DFS를 활용한 다양한 문제들을 풀어보며 실력을 쌓아가는 것이 좋습니다. 대표적인 문제로는:
- 미로 탐색
- 연결 요소 찾기
- 사이클 검출
8. 결론
이번 강좌를 통해 깊이 우선 탐색의 기본 개념과 자바에서의 구현 방법을 배웠습니다. 그래프 문제는 코딩테스트에서 자주 출제되므로 반드시 숙지하고 연습해보시기 바랍니다. 다음 강좌에서는 다른 탐색 알고리즘인 너비 우선 탐색(BFS)에 대해 다뤄보겠습니다.