코딩테스트

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
    }
}