[알고리즘] DFS와 BFS

⭐ DFS (깊이 우선 탐색)

DFS(Depth-First Search)는 시작 노드에서 깊이 들어가 최대한 멀리 가다가 더 이상 갈 수 없게 되면, 이전 노드로 돌아와서 다른 경로를 탐색하는 알고리즘입니다.

이 과정에서 스택(Stack)을 사용하거나 재귀 호출을 통해 구현됩니다.

DFS는 LIFO(후입선출) 방식으로 작동하여, 나중에 들어간 노드가 먼저 나오게 됩니다.

주로 경로 탐색, 모든 경우의 수 탐색 등에 사용됩니다.

✅ 구현 방법

1️⃣ 스택

스택을 이용한 DFS 구현은 다음과 같이 할 수 있습니다. 노드를 방문할 때마다 스택에 추가하고, 더 이상 갈 수 없는 경우에는 스택에서 팝(pop)하여 이전 노드로 돌아갑니다.

import java.util.*;

public class DFSStack {
    private Map<Integer, List<Integer>> graph;

    public DFSStack() {
        graph = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        graph.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
        graph.computeIfAbsent(w, k -> new ArrayList<>()).add(v); // 무방향 그래프
    }

    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                System.out.println("Visited: " + node);
                for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        DFSStack dfs = new DFSStack();
        dfs.addEdge(1, 2);
        dfs.addEdge(1, 3);
        dfs.addEdge(2, 4);
        dfs.addEdge(2, 5);
        dfs.addEdge(3, 6);
        dfs.dfs(1);
    }
}

 

2️⃣ 재귀 호출

재귀를 이용한 DFS 구현은 간단하고 직관적입니다. 방문할 노드를 함수 호출로 처리하여 더욱 깔끔하게 표현할 수 있습니다.

import java.util.*;

public class DFSRecursive {
    private Map<Integer, List<Integer>> graph;

    public DFSRecursive() {
        graph = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        graph.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
        graph.computeIfAbsent(w, k -> new ArrayList<>()).add(v); // 무방향 그래프
    }

    public void dfs(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.println("Visited: " + node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFSRecursive dfs = new DFSRecursive();
        dfs.addEdge(1, 2);
        dfs.addEdge(1, 3);
        dfs.addEdge(2, 4);
        dfs.addEdge(2, 5);
        dfs.addEdge(3, 6);
        Set<Integer> visited = new HashSet<>();
        dfs.dfs(1, visited);
    }
}

 

✅ 방문 표시 시점

DFS에서는 스택에서 노드를 팝할 때 방문 표시를 합니다. 이는 각 노드가 한 번만 방문되도록 보장하며, 무한 루프를 방지합니다.

 

✅ 사용 목적

• 경로의 존재 여부를 판단할 떄
• 그래프의 모든 경로를 탐색할 때
• 싸이클 탐지

 

⭐ BFS (너비 우선 탐색)

BFS(Breadth-First Search)는 시작 노드에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다.

큐(Queue)를 사용하여 현재 노드를 방문하고 그 노드에 연결된 모든 노드를 탐색한 후, 그 다음 단계로 넘어갑니다.

BFS는 FIFO(선입선출) 방식으로 작동하여, 먼저 들어간 노드가 먼저 나오게 됩니다.

최단 경로 문제나 레벨 탐색에 주로 사용됩니다.

✅ 구현 방법

BFS는 큐를 사용하여 구현할 수 있습니다. 노드를 방문할 때마다 큐에 추가하고, 모든 이웃 노드를 탐색한 후 큐에서 노드를 제거합니다.

import java.util.*;

public class BFS {
    private Map<Integer, List<Integer>> graph;

    public BFS() {
        graph = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        graph.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
        graph.computeIfAbsent(w, k -> new ArrayList<>()).add(v); // 무방향 그래프
    }

    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.println("Visited: " + node);
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS bfs = new BFS();
        bfs.addEdge(1, 2);
        bfs.addEdge(1, 3);
        bfs.addEdge(2, 4);
        bfs.addEdge(2, 5);
        bfs.addEdge(3, 6);
        bfs.bfs(1);
    }
}

 

✅ 방문 표시 시점

BFS에서는 큐에 노드를 푸시할 때 방문 표시를 합니다. 이를 통해 각 노드가 한 번만 방문되도록 하여 무한 루프를 방지합니다.

 

✅ 사용 목적

• 가중치가 없는 그래프의 최단 경로를 탐색할 때
• 레벨 탐색 및 그래프의 구조를 파악할 때

 

💡 DFS or BFS 선택 방법

1️⃣ 모든 경로 탐색 문제 = DFS

예시: 그래프에서 두 노드 A와 B 사이의 모든 경로를 찾는 문제.

• 문제 설명: 주어진 그래프에서 노드 A에서 노드 B까지 도달할 수 있는 모든 경로를 나열합니다. 경로는 중복된 노드를 포함할 수도 있습니다.
• 해결 방법: DFS를 사용하여 A에서 시작해 가능한 모든 경로를 탐색합니다. 노드 B에 도달할 때마다 경로를 기록합니다.

차이점:

• 목적: 경로의 수를 세고, 각각의 경로를 나열하는 것이 목적입니다.
• 예시 결과: A → C → B, A → D → B, A → C → D → B 등.

2️⃣ 최단 경로 문제 = BFS

예시: 두 노드 A와 B 사이의 최단 경로를 찾는 문제.

• 문제 설명: 가중치가 동일한 그래프에서 노드 A에서 노드 B까지 가는 최단 경로를 찾습니다. 가중치가 있는 그래프에서는 다익스트라 알고리즘이나 벨만-포드 알고리즘을 사용할 수 있습니다.
• 해결 방법: BFS를 사용하여 최단 경로를 탐색합니다.

차이점:

• 목적: 노드 A에서 노드 B까지의 최단 경로를 찾는 것이 목적입니다.
• 예시 결과: A → C → B (비용이나 거리 측면에서 가장 짧은 경로).

 

🚩 요약

• 모든 경로 탐색: 가능한 모든 경로를 나열하고, 각 경로의 중복 여부를 고려합니다.
• 최단 경로: 특정 기준(거리, 비용 등)을 만족하는 가장 짧은 경로를 찾습니다.