[알고리즘/JAVA] DFS와 BFS

⭐ DFS와 BFS란 무엇인가?

 

• DFS (Depth-First Search, 깊이 우선 탐색): 그래프나 트리에서 한 경로를 끝까지 탐색하고, 더 이상 탐색할 노드가 없으면 다시 이전 노드로 돌아와 다른 경로를 탐색합니다. 깊이 방향으로 탐색하는 방식이므로, 스택이나 재귀를 사용하여 구현됩니다.
• BFS (Breadth-First Search, 너비 우선 탐색): 시작 노드에서부터 인접한 노드를 먼저 탐색한 후, 다시 그 인접 노드의 인접 노드들을 탐색하는 방식입니다. 주로 큐를 사용하여 구현됩니다.

 

⭐ DFS와 BFS의 차이점

특징	DFS	BFS
탐색 방식	깊이 우선, 한 경로를 끝까지 탐색	너비 우선, 인접한 노드를 모두 탐색
자료 구조	스택(재귀로 구현 가능)	큐
경로 탐색	가능한 경로를 빠르게 찾음	최단 경로 탐색에 유리
메모리 사용량	재귀 호출에 따른 스택 메모리 사용 증가	큐에 노드 저장 공간 필요
대표적 사용 예시	백트래킹, 퍼즐 문제	최단 경로 찾기, 최단 이동 횟수 계산

 

 

⭐ DFS와 BFS의 기본 코드 구조

✅ DFS 기본 코드

import java.util.*;

public class GraphDFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    // 그래프에 노드와 간선을 추가하는 메서드
    public void addEdge(int src, int dest) {
        graph.putIfAbsent(src, new ArrayList<>());
        graph.get(src).add(dest);
    }

    // DFS 구현 (재귀 사용)
    public void dfs(int node) {
        if (visited.contains(node)) return;
        visited.add(node);
        System.out.print(node + " ");

        // 현재 노드와 연결된 모든 노드에 대해 DFS 재귀 호출
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graphDFS = new GraphDFS();
        graphDFS.addEdge(0, 1);
        graphDFS.addEdge(0, 2);
        graphDFS.addEdge(1, 2);
        graphDFS.addEdge(2, 0);
        graphDFS.addEdge(2, 3);
        graphDFS.addEdge(3, 3);

        System.out.println("DFS 탐색 결과:");
        graphDFS.dfs(2);
    }
}

✅ BFS 기본 코드

import java.util.*;

public class GraphBFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    // 그래프에 노드와 간선을 추가하는 메서드
    public void addEdge(int src, int dest) {
        graph.putIfAbsent(src, new ArrayList<>());
        graph.get(src).add(dest);
    }

    // BFS 구현 (큐 사용)
    public void bfs(int startNode) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        visited.add(startNode);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // 현재 노드와 연결된 모든 노드를 큐에 추가
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphBFS graphBFS = new GraphBFS();
        graphBFS.addEdge(0, 1);
        graphBFS.addEdge(0, 2);
        graphBFS.addEdge(1, 2);
        graphBFS.addEdge(2, 0);
        graphBFS.addEdge(2, 3);
        graphBFS.addEdge(3, 3);

        System.out.println("BFS 탐색 결과:");
        graphBFS.bfs(2);
    }
}

 

⭐ DFS와 BFS 응용 방법

 

• DFS 응용
  • 백트래킹: 퍼즐, 조합 및 순열 찾기 문제에서 모든 가능한 경우의 수를 탐색하는 데 사용합니다. 예를 들어, 미로 문제나 N-Queens 문제에서 특정 경로가 유효한지 확인하며 풀 수 있습니다.
  • 연결 요소 찾기: 그래프의 각 연결 요소를 찾는 데 DFS를 사용하여, 하나의 DFS 탐색이 끝나면 연결 요소의 크기나 구성 요소를 기록할 수 있습니다.
• BFS 응용
  • 최단 경로 찾기: 가중치가 없는 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 데 유용합니다. 예를 들어, 미로에서 출발점에서 도착점까지 가장 적은 이동 횟수로 이동할 때 BFS를 사용할 수 있습니다.
  • 단계별 탐색 문제: 너비 우선 탐색은 단계별로 노드를 방문하므로, BFS는 특정 노드에서 일정 단계만큼 떨어진 노드를 찾는 문제에 적합합니다.

 

⭐ 예제 문제 및 응용 코드 예시

1️⃣ 미로 탐색 문제

• 문제: 미로의 시작점에서 출발해 목표점까지 이동하는데, 이동할 수 있는 최단 거리를 구합니다. BFS를 사용하여 미로를 탐색하고 이동 거리를 계산합니다.

import java.util.*;

class MazeSolver {
    private static final int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우 이동
    private static final int[] dy = {0, 0, -1, 1};

    public int shortestPath(int[][] maze, int startX, int startY, int endX, int endY) {
        int rows = maze.length;
        int cols = maze[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];

        queue.add(new int[]{startX, startY, 0});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1], dist = cell[2];

            if (x == endX && y == endY) return dist;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && maze[nx][ny] == 0 && !visited[nx][ny]) {
                    queue.add(new int[]{nx, ny, dist + 1});
                    visited[nx][ny] = true;
                }
            }
        }
        return -1; // 목표 지점에 도달할 수 없는 경우
    }

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 0},
            {0, 0, 0, 0, 0}
        };
        MazeSolver solver = new MazeSolver();
        System.out.println("최단 경로 길이: " + solver.shortestPath(maze, 0, 0, 4, 4));
    }
}

2️⃣ 모든 경로 탐색 문제

• 문제: 주어진 그래프에서 특정 시작점과 종료점 간 모든 가능한 경로를 찾습니다. 이 문제는 DFS로 풀 수 있으며, 백트래킹을 통해 경로를 저장합니다.

import java.util.*;

public class AllPathsDFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    // 그래프에 노드와 간선을 추가하는 메서드
    public void addEdge(int src, int dest) {
        graph.putIfAbsent(src, new ArrayList<>());
        graph.get(src).add(dest);
    }

    // 모든 경로 찾기 - DFS 사용
    public void findAllPaths(int start, int end, List<Integer> path, List<List<Integer>> allPaths) {
        path.add(start);
        if (start == end) {
            allPaths.add(new ArrayList<>(path));
        } else {
            for (int neighbor : graph.getOrDefault(start, new ArrayList<>())) {
                if (!path.contains(neighbor)) {
                    findAllPaths(neighbor, end, path, allPaths);
                }
            }
        }
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        AllPathsDFS graph = new AllPathsDFS();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        List<List<Integer>> allPaths = new ArrayList<>();
        graph.findAllPaths(2, 3, new ArrayList<>(), allPaths);
        
        System.out.println("모든 경로:");
        for (List<Integer> path : allPaths) {
            System.out.println(path);
        }
    }
}

 

 

🚩 결론

DFS와 BFS는 그래프 탐색의 핵심 알고리즘으로, 각자의 특징과 적합한 문제 유형을 이해하는 것이 중요합니다. 문제 상황에 따라 DFS나 BFS 중 적합한 알고리즘을 선택하여 효율적으로 문제를 해결해보는 연습을 해보시는 걸 추천드립니다!

코딩 테스트에서는 기본 구현뿐 아니라 이를 응용한 백트래킹, 최단 경로 탐색 등의 문제도 자주 출제되니 다양한 예제를 통해 충분히 연습해 보길 권장합니다!!