[TIL] 알고리즘 BFS & DFS 정리

 

알고리즘 문제를 풀다 보면 격자, 네트워크, 지도, 트리 등 연결 구조를 다루는 경우가 많습니다.

이때 필요한 것이 바로 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)입니다.

---

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

출발점에서 한 방향을 정하면 끝까지 깊게 들어간 뒤, 더 이상 갈 수 없을 때 다시 되돌아와서 다른 경로를 탐색하는 방식입니다.

재귀 함수나 스택(Stack)으로 구현할 수 있습니다.

ex) 미로에 들어간 쥐가 한쪽 길을 끝까지 파고 들어갔다가 막히면 다시 돌아와서 다른 길을 찾는 것과 같습니다.

 

- 장점 : 구현이 간단하고 코드가 짧음

- 단점 : 재귀 호출로 인해 입력 크기가 크면 스택 오버플로우 위험

- 적합한 문제 : 모든 경우를 따져야 하는 문제, 영역 탐색 문제

 

 

 

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

출발점에서 시작하여 가까운 칸부터 차례로 방문하고, 그다음 레벨로 확장해 나가는 방식입니다.

큐(Queue)를 사용하여 구현합니다.

ex) 물을 한 방울 떨어뜨리면 파동이 퍼지듯 모든 방향으로 동시에 퍼져나가는 것과 같습니다. 

 

- 장점 : 최단 거리/최소 시간문제 해결에 탁월

- 단점 : 구현이 DFS보다 다소 길어질 수 있음

- 적합한 문제 : 최단 거리, 최소 시간 문제

 

3. 구현 방식의 차이

DFS : 깊게 들어가는 성격 → 재귀 호출/스택 사용

BFS : 가까운 곳부터 탐색하는 성격 → 큐 사용

구분	DFS	BFS
자료구조	스택(재귀/직접)	큐
탐색 순서	깊이 우선	너비 우선
최단거리 보장	X	O
대표 문제	알파벳, 연구소	토마토, 탈출

DFS / BFS

 

4. 수도코드

DFS (재귀)

dfs(r, c):
  방문[r][c] = true
  size = 1
  for 방향 d:
    nr, nc = r+dr[d], c+dc[d]
    if (nr, nc)가 범위 안이고, 방문X이고, map[nr][nc]==1:
       size += DFS(nr, nc)
  return size

 

BFS (큐)

bfs(sr, sc):
  방문[sr][sc] = true
  큐에 (sr, sc) 삽입
  size = 0
  while 큐가 비어있지 않음:
    (r, c) = 큐.pop()
    size += 1
    for 방향 d:
      nr, nc = r+dr[d], c+dc[d]
      if (nr, nc)가 범위 안이고, 방문X이고, map[nr][nc]==1:
         방문[nr][nc] = true
         큐에 (nr, nc) 삽입
  return size

 

5. 예시 문제 풀이

BOJ 1926 그림

https://www.acmicpc.net/problem/1926

 

풀이 과정
1. 이중 for문으로 모든 칸 확인
2. 아직 방문하지 않았고 1이면 새로운 그림 발견
3. DFS 또는 BFS로 그림 크기(size) 탐색
4. 그림 개수 증가, 최대 크기 갱신

 

(1) DFS 풀이

import java.util.*;

public class Main {  
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] arr;
    static int n, m;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n][m];
        int count = 0;
        int max = 0;

        // 각자 방에서 갈 수 있는 값 확인
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(arr[i][j] == 1) {
                    int sum = check(i, j);
                    count++;
                    if(max < sum) {
                        max = sum;
                    }
                }
            }
        }
        System.out.println(count);
        System.out.println(max);
    }
    
    static int check(int x, int y) {
        int xx = x;
        int yy = y;
        arr[xx][yy] = 0; // 방문 체크
        int size = 1;
        for(int i = 0; i < 4; i++) {
            int cx = xx + dx[i];
            int cy = yy + dy[i];
            if(cx >= 0 && cy >= 0 && cx < n && cy < m && arr[cx][cy] != 0) {
                arr[cx][cy] = 0;
                size += check(cx, cy);
            }
        }
        return size;
    }
}

 

(2) BFS 풀이

import java.util.*;

public class Main {
	static int N, M;
	static int[][] arr;
	static boolean[][] visited;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N][M];
		visited = new boolean[N][M];

		// 0은 색칠이 안된 부분, 1은 색칠이 된 부분
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		int numPictures = 0; // 총 그림의 수
		int maxSize = 0; // 가장 큰 그림의 크기
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1 && !visited[i][j]) {
					numPictures++;
					int size = bfs(i, j);
					if (size > maxSize) {
						maxSize = size;
					}
				}
			}
		}
		
		System.out.println(numPictures);
		System.out.println(maxSize);

	}

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

		visited[x][y] = true;
		int size = 1; // 현재 그림 크기

		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			int cx = current[0];
			int cy = current[1];

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

				if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && arr[nx][ny] == 1) {
					visited[nx][ny] = true;
					queue.add(new int[] { nx, ny });
					size++;
				}
			}
		}
		return size;
	}
}

 

(3) 성능 비교

DFS, BFS 순

이번 문제에서는 BFS 풀이가 DFS보다 더 빠르게 동작하는 것을 확인했습니다.
하지만 항상 BFS가 DFS보다 빠른 것은 아닙니다.

 

- DFS: 재귀 호출을 사용해 코드가 간단하지만, 깊은 탐색에서는 스택 오버헤드 발생 가능

- BFS: 큐를 사용해 코드가 길어지지만, 재귀 호출이 없어서 대규모 입력에서도 안정적

 

즉, 성능 차이는 입력 크기와 구현 방식(재귀/반복, 자료구조 선택)에 따라 달라집니다.
이번 케이스에서는 BFS가 더 좋은 성능을 보였지만, 다른 상황에서는 DFS가 더 유리할 수도 있습니다.

 

알고리즘 문제를 풀기 앞서
"최단 거리/최소 시간문제냐?" vs "모든 경우/영역 탐색 문제냐?"를 구분하세요 !
그에 따라 DFS와 BFS 중 적절한 방법을 빠르게 선택하는 것이 실전 알고리즘 풀이의 핵심입니다.