[25/11/08 TIL] DFS / BFS

📚 학습 목표

• DFS/BFS의 동작 원리 이해
• 스택과 큐를 활용한 구현
• 재귀를 이용한 DFS 구현
• 실전 문제 풀이 (백준 1012, 2667, 1260)

---

🔍 DFS와 BFS란?

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

• 자료구조: 큐(Queue) - FIFO
• 특징: 가까운 곳부터 레벨별로 탐색
• 장점: 최단 거리 보장
• 탐색 순서: 거리 1 → 거리 2 → 거리 3...

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

• 자료구조: 스택(Stack) 또는 재귀
• 특징: 한 방향 끝까지 탐색 후 백트래킹
• 단점: 최단 거리 보장 X
• 탐색 순서: 한 경로를 끝까지 → 돌아와서 다른 경로

---

💡 핵심 개념

1. 왜 BFS는 최단 거리를 보장할까?

BFS는 레벨별로 탐색하기 때문이다.

시작점 S에서 출발
- 거리 1인 곳: A, B 모두 탐색
- 거리 2인 곳: C, D, E 모두 탐색
- 거리 3인 곳: F, G 모두 탐색

목표 지점 E에 도착하는 순간, 그것이 최단 거리다. 왜냐하면 더 짧은 경로가 있었다면 이미 탐색했을 것이기 때문이다.

DFS는 거리 순서와 상관없이 깊이 우선으로 탐색하므로 최단 거리를 보장하지 못한다.

2. 방향 배열의 활용

상하좌우 이동을 깔끔하게 표현하는 방법:

int[] dx = {-1, 1, 0, 0};  // 상, 하, 좌, 우 (행 변화)
int[] dy = {0, 0, -1, 1};  // 열 변화

for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 상하좌우 탐색
}

---

🛠️ 구현 방법

BFS 구현 (큐 사용)

static void bfs(int startX, int startY) {
    Queue<int[]> q = new LinkedList<>();
    visited[startX][startY] = true;
    q.add(new int[]{startX, startY});
    
    while (!q.isEmpty()) {
        int[] current = q.poll();
        int x = current[0];
        int y = current[1];
        
        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 범위 체크, 벽 체크, 방문 체크
            if (nx >= 0 && nx < N && ny >= 0 && ny < N 
                && grid[nx][ny] != 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.add(new int[]{nx, ny});
            }
        }
    }
}

DFS 구현 (재귀 사용)

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 && nx < N && ny >= 0 && ny < N 
            && grid[nx][ny] != 0 && !visited[nx][ny]) {
            dfs(nx, ny);  // 재귀 호출
        }
    }
}

핵심: 스택에 넣는 대신 dfs(nx, ny)로 바로 그 위치에서 탐색을 시작한다.

---

🎯 실전 문제 풀이

백준 1012 - 유기농 배추

문제 유형: 연결된 컴포넌트 개수 세기

핵심 패턴:

int count = 0;
for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        if (grid[i][j] == 1 && !visited[i][j]) {
            count++;        // 새 그룹 발견
            dfs(i, j);      // 그룹 전체 방문 처리
        }
    }
}

백준 2667 - 단지번호붙이기

추가 요구사항: 각 그룹의 크기를 저장하고 오름차순 정렬

해결 방법:

static int dfs(int x, int y) {
    visited[x][y] = true;
    int count = 1;  // 현재 집
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (조건) {
            count += dfs(nx, ny);  // 재귀로 받은 값 누적
        }
    }
    
    return count;
}

// main에서
List<Integer> results = new ArrayList<>();
if (grid[i][j] == 1 && !visited[i][j]) {
    int size = dfs(i, j);
    results.add(size);
}
Collections.sort(results);

백준 1260 - DFS와 BFS

새로운 점: 2차원 격자가 아닌 그래프 입력

그래프 저장 방법 (인접 리스트):

List<Integer>[] graph = new ArrayList[N+1];

// 초기화
for (int i = 1; i <= N; i++) {
    graph[i] = new ArrayList<>();
}

// 간선 입력 (양방향)
graph[a].add(b);
graph[b].add(a);

// 정렬 (작은 번호부터 방문)
for (int i = 1; i <= N; i++) {
    Collections.sort(graph[i]);
}

DFS (그래프 버전):

static void dfs(int node) {
    visited[node] = true;
    System.out.print(node + " ");
    
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

BFS (그래프 버전):

static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;
    q.add(start);
    
    while (!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");
        
        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                q.add(next);
            }
        }
    }
}

---

📊 문제 유형별 정리

문제 유형 적합한 알고리즘 이유

최단 거리	BFS 필수	레벨별 탐색으로 최단 거리 보장
연결 요소 개수	DFS/BFS 둘 다	모든 노드 방문이 목적
경로 존재 여부	DFS/BFS 둘 다	도달 가능 여부만 확인
모든 경로 탐색	DFS	깊이 우선으로 경로 완전 탐색

---

🎓 배운 점

1. 인접성의 중요성

초반에 이중 for문으로 전체 grid를 순회하려고 했는데, DFS/BFS는 현재 위치에서 인접한 칸만 탐색해야 한다. 이게 그래프 탐색의 본질이다.

2. 출력 위치에 따른 탐색 순서

// 큐/스택에 넣을 때 출력
if (조건) {
    q.add(new int[]{nx, ny});
    System.out.println("방문");  // 넣을 때
}

// 큐/스택에서 꺼낼 때 출력
int[] current = q.poll();
System.out.println("방문");  // 꺼낼 때

꺼낼 때 출력해야 실제 탐색 순서를 확인할 수 있다.

3. static vs 인자 전달

• 알고리즘 문제: static 전역 변수 (빠른 구현)
• 실제 프로젝트: 명시적 인자 전달 (side effect 최소화)

상황에 따라 적절히 선택하자.

4. 그래프 입력 처리

• 2차원 격자: int[][] grid, dx/dy 배열
• 일반 그래프: List<Integer>[], 인접 리스트, 정렬 필수