카테고리 없음

(알고리즘) DFS vs BFS (그래프 탐색 기법 정리)

불광동 물주먹 2025. 5. 3. 16:54

DFS vs BFS (그래프 탐색 기법 정리)


1. 그래프 탐색이란?

그래프 탐색(Graph Traversal)이란, 어떤 노드(정점, Vertex)에서 시작해서 연결된 모든 노드를 빠짐없이 방문하는 과정이다.
그래프는 다음 두 요소로 구성된다:

  • Vertex (정점): 탐색의 대상이 되는 지점 (예: 사람, 도시, 방 등)
  • Edge (간선): 정점 간의 연결 (예: 친구 관계, 도로, 벽 없는 통로 등)

그래프는 연결되어 있는 방식에 따라 다양한 문제(미로 탐색, 단지 번호 붙이기, 친구 관계 등)에 응용될 수 있다.


2. 탐색 기법 종류

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

  • 한 방향으로 쭉 들어가며 끝까지 탐색한 뒤, 다시 돌아와서 다른 방향 탐색
  • 자식의 자식까지 내려감, 더 이상 갈 곳이 없을 때 되돌아오는 방식
  • 주로 재귀 함수 또는 스택으로 구현
  • 백트래킹, 조합, 순열, 영역 탐색 등에 사용됨
동작 순서:
1. 현재 노드를 방문처리
2. 인접한 노드 중 방문하지 않은 노드로 이동 (재귀적으로)
3. 갈 곳이 없으면 이전 단계로 돌아감 (Backtracking)

구현 도구:

  • 재귀 함수
  • 또는 명시적인 스택 자료구조

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

  • 시작 노드에서 가까운 정점부터 넓게 퍼지듯이 탐색
  • 형제 노드(같은 깊이의 노드)를 먼저 모두 방문하고, 다음 깊이로 진행
  • 최단 거리 탐색, 계층 구조 순회, 단계별 접근 등에 사용됨
동작 순서:
1. 시작 노드를 방문 처리 후 큐에 삽입
2. 큐에서 노드를 꺼내며 인접한 노드 중 방문하지 않은 노드를 큐에 삽입
3. 큐가 빌 때까지 반복

구현 도구:

  • 큐(Queue)

3. DFS / BFS 비교


 

항목 DFS BFS
기본 전략 깊이 우선 너비 우선
자료구조 스택 (또는 재귀)
구현 방식 보통 재귀 사용 반복문 + 큐
방문 순서 깊이 → 형제 형제 → 깊이
용도 경로 탐색, 백트래킹 최단 거리, 단계별 확산
성능 깊은 분기 탐색에 유리 넓은 범위 탐색에 유리
시간 복잡도 O(V + E) O(V + E)
 

※ V: 정점 수, E: 간선 수


4. DFS 구현 예시 (JAVA)

 
public class DFSExample {
    static int[][] graph;
    static boolean[][] visited;
    static int n;

    // 상하좌우
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static void dfs(int x, int y) {
        visited[x][y] = true;

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

            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (!visited[nx][ny] && graph[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

5. BFS 구현 예시 (JAVA)

import java.util.LinkedList;
import java.util.Queue;

public class BFSExample {
    static int[][] graph;
    static boolean[][] visited;
    static int n;

    // 상하좌우
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int curX = pos[0];
            int curY = pos[1];

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

                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

6. DFS vs BFS 선택 기준

 

상황  추천 탐색  방식
모든 경우의 수 탐색 DFS (백트래킹)
경로의 최단 거리 탐색 BFS
조합, 순열 문제 DFS
가까운 노드 우선 처리 BFS
미로처럼 복잡한 구조 탐색 DFS or BFS 모두 가능 (조건에 따라 선택)
 

7. 방문 여부 체크 방법

그래프에서 중복 방문을 막기 위해 방문 여부 기록이 필수이다.
방법은 다음과 같다:

  • 2차원 배열 탐색: visited = [[False]*n for _ in range(n)] 또는 입력 배열 자체에 표시 (graph[x][y] = 0)
  • 일반 그래프 탐색: visited = [False] * (정점 수 + 1)

마무리 요약

  • DFS는 한 방향으로 깊이 파고들며 재귀적으로 탐색
  • BFS는 가까운 노드부터 넓게 순차적으로 탐색
  • 문제의 성격(최단 거리, 모든 경우의 수 등)에 따라 적절히 선택해야 한다
  • DFS는 스택, BFS는 기반의 흐름을 따른다