[알고리즘/Java] DFS (Depth-First Search, 깊이 우선 탐색), BFS (Breadth-First Search, 너비 우선 탐색)

 

 

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색 알고리즘의 대표적인 방식입니다.

---

1. DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 한 노드를 방문하면 더 이상 갈 수 없을 때까지 깊이 들어가는 방식으로 탐색하는 알고리즘입니다.
스택(Stack)이나 재귀(Recursion)을 이용해서 구현할 수 있습니다.

DFS 코드

import java.util.*;

public class GraphDFS {
    private int vertices; // 노드 개수
    private LinkedList<Integer>[] adjList; // 인접 리스트

    // 그래프 초기화
    public GraphDFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 간선 추가
    public void addEdge(int v, int w) {
        adjList[v].add(w); // 방향 그래프 (v -> w)
    }

    // DFS 실행 함수
    public void DFS(int start) {
        boolean[] visited = new boolean[vertices]; // 방문 여부 저장
        System.out.println("DFS 탐색 순서:");
        DFSUtil(start, visited);
        System.out.println();
    }

    // DFS 재귀 함수
    private void DFSUtil(int node, boolean[] visited) {
        visited[node] = true; // 현재 노드를 방문 처리
        System.out.print(node + " "); // 방문한 노드 출력

        for (int neighbor : adjList[node]) { // 인접 노드 확인
            if (!visited[neighbor]) { // 방문하지 않은 노드라면 재귀 호출
                DFSUtil(neighbor, visited);
            }
        }
    }

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

        g.DFS(0);
    }
}

---

DFS 코드 설명

1. 그래프 표현
   • LinkedList<Integer>[] adjList 를 사용하여 인접 리스트 방식으로 그래프를 표현합니다.
   • addEdge(v, w) 함수에서 간선을 추가합니다.
2. DFS 탐색 함수
   • DFS(start)는 방문 여부를 저장하는 visited 배열을 만들고 탐색을 시작합니다.
   • DFSUtil(node, visited)는 재귀를 통해 깊이 우선 탐색을 수행합니다.
   • 현재 노드를 방문 처리하고 인접 노드들을 재귀적으로 방문합니다.
3. 실행 예시
   • 0에서 시작 → 1 방문 → 3 방문 → 5 방문 → 4 방문 → 2 방문
4. DFS 탐색 순서: 0 1 3 5 4 2

---

 

2. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 한 노드에서 시작하여 모든 인접 노드를 방문한 후 다음 깊이로 이동하는 방식입니다.
일반적으로 큐(Queue)를 사용하여 구현합니다.

BFS 코드

import java.util.*;

public class GraphBFS {
    private int vertices;
    private LinkedList<Integer>[] adjList;

    // 그래프 초기화
    public GraphBFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 간선 추가
    public void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // BFS 실행 함수
    public void BFS(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        System.out.println("BFS 탐색 순서:");
        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 꺼내기
            System.out.print(node + " ");

            for (int neighbor : adjList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        System.out.println();
    }

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

        g.BFS(0);
    }
}

---

BFS 코드 설명

1. 그래프 표현
   • DFS와 마찬가지로 LinkedList<Integer>[] adjList 를 사용해 인접 리스트 방식으로 그래프를 구현합니다.
2. BFS 탐색 함수
   • Queue<Integer> 를 사용하여 방문할 노드를 관리합니다.
   • 방문한 노드를 큐에서 꺼낸 후, 그 노드의 인접 노드를 큐에 추가합니다.
   • 방문한 노드는 visited 배열로 체크하여 중복 방문을 방지합니다.
3. 실행 예시
   • 0에서 시작 → 1, 2 방문 → 3, 4 방문 → 5 방문
4. BFS 탐색 순서: 0 1 2 3 4 5

---

 

3. DFS (깊이 우선 탐색, 2D 배열)

DFS를 2차원 배열에서 활용하는 경우는 주로 미로 탐색, 섬 찾기(connected component) 문제에서 많이 사용됩니다.
방문한 노드를 체크하면서 상, 하, 좌, 우 이동을 처리하면 됩니다.

DFS 코드 (2D 배열)

import java.util.*;

public class DFS2D {
    private static int[][] graph = {
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 1, 1},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };

    private static int rows = graph.length;
    private static int cols = graph[0].length;
    private static boolean[][] visited = new boolean[rows][cols];

    // 상, 하, 좌, 우 방향 벡터
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    // DFS 실행 함수
    public static void DFS(int x, int y) {
        if (x < 0 || y < 0 || x >= rows || y >= cols) return; // 범위 체크
        if (visited[x][y] || graph[x][y] == 0) return; // 방문했거나 갈 수 없는 곳

        visited[x][y] = true; // 방문 처리
        System.out.println("방문: (" + x + ", " + y + ")");

        // 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            DFS(nx, ny);
        }
    }

    public static void main(String[] args) {
        System.out.println("DFS 탐색 결과:");
        DFS(0, 0); // (0, 0)에서 탐색 시작
    }
}

---

DFS 코드 설명

1. 그래프 표현
   • graph 는 2차원 배열로, 1이면 이동 가능, 0이면 이동 불가능한 노드라고 가정.
   • visited[][] 배열을 사용해 방문 여부를 체크.
2. DFS 탐색
   • 현재 위치에서 4방향(상, 하, 좌, 우)으로 이동하면서 탐색.
   • 범위를 벗어나거나, 방문했거나, 0인 경우 탐색 종료.
   • 방문하면 visited[x][y] = true로 체크.
3. 실행 예시
   • (0, 0)에서 시작해서 연결된 1을 따라가면서 탐색.
4. DFS 탐색 결과: 방문: (0, 0) 방문: (1, 0) 방문: (1, 1) 방문: (0, 1)

---

4. BFS (너비 우선 탐색, 2D 배열)

BFS는 최단 거리 문제(미로 찾기), 단계별 탐색(전염병 퍼지는 과정) 등에 자주 사용됩니다.
보통 Queue를 활용해서 탐색을 진행합니다.

BFS 코드 (2D 배열)

import java.util.*;

public class BFS2D {
    private static int[][] graph = {
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 1, 1},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };

    private static int rows = graph.length;
    private static int cols = graph[0].length;
    private static boolean[][] visited = new boolean[rows][cols];

    // 상, 하, 좌, 우 방향 벡터
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    // BFS 실행 함수
    public static void BFS(int startX, int startY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        System.out.println("BFS 탐색 결과:");

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

            System.out.println("방문: (" + x + ", " + y + ")");

            // 4방향 탐색
            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 && !visited[nx][ny] && graph[nx][ny] == 1) {
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS(0, 0); // (0, 0)에서 탐색 시작
    }
}

---

BFS 코드 설명

1. 그래프 표현
   • DFS와 동일한 2차원 배열 (graph[][]) 사용.
2. BFS 탐색
   • Queue<int[]> 를 이용해 탐색할 좌표를 저장.
   • 큐에서 꺼낸 후, 4방향을 탐색하며 이동 가능하면 큐에 추가.
   • visited[][] 체크하여 중복 방문 방지.
3. 실행 예시
   • BFS는 가까운 곳부터 탐색하며 퍼져나감.
4. BFS 탐색 결과: 방문: (0, 0) 방문: (0, 1) 방문: (1, 0) 방문: (1, 1)

---

 

DFS vs BFS 비교

알고리즘	방식	자료구조	탐색 순서
DFS	깊이 우선 탐색	스택(재귀)	한 경로를 끝까지 탐색 후 백트래킹
BFS	너비 우선 탐색	큐	가까운 노드부터 탐색

언제 DFS를 쓰고, 언제 BFS를 써야 할까?

• DFS
  • 경로 탐색(예: 미로 찾기)
  • 백트래킹(예: 조합, 순열 문제)
  • 그래프의 연결 요소 찾기
• BFS
  • 최단 경로 문제 (예: 최단 거리 찾기)
  • 레벨별 탐색 (예: 네트워크 전파)

---

정리

• DFS는 재귀 또는 스택을 이용해 깊이 우선 탐색.
• BFS는 큐를 이용해 너비 우선 탐색.
• DFS는 깊이 먼저 탐색하여 백트래킹, BFS는 가까운 노드부터 탐색.
• 용도에 따라 DFS 또는 BFS를 선택하여 사용.