코딩테스트
DFS(Depth-First Search) 깊이 우선 탐색
NellKiM
2025. 5. 30. 14:22
DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리에서 한 방향으로 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 다시 돌아와서 다른 방향을 탐색하는 알고리즘
✅ 핵심 개념
- 시작 노드에서 한 방향으로 쭉 내려감
- 더 이상 갈 곳이 없으면 백트래킹(되돌아가기)
- 스택(stack) 또는 재귀(recursion) 를 사용해 구현
✅ 동작 방식
A
├── B
│ └── D
└── C
✅ DFS 구현 방법
import java.util.*;
public class DFSExample {
public static void dfs(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
Stack<String> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
String node = stack.pop();
if (!visited.contains(node)) {
System.out.print(node + " ");
visited.add(node);
// 스택은 후입선출이므로, 역순으로 넣어야 순서대로 탐색됨
List<String> neighbors = graph.getOrDefault(node, new ArrayList<>());
Collections.reverse(neighbors);
for (String neighbor : neighbors) {
stack.push(neighbor);
}
}
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("D"));
graph.put("C", new ArrayList<>());
graph.put("D", new ArrayList<>());
dfs(graph, "A"); // 출력: A B D C
}
}