← 알고리즘 목록
그래프 시간 O(행 × 열) · 공간 O(행 × 열)

DFS 플러드 필

격자를 훑다가 땅을 만나면 거기서 이어진 칸을 깊이 우선으로 모두 지워, 이어진 덩어리를 하나씩 셉니다.

대표 문제

언제 쓰나

격자나 그래프에서 서로 이어진 덩어리를 다룰 때 씁니다.

  • 이어진 덩어리가 몇 개인지 셉니다. 섬의 개수, 방의 개수 같은 문제입니다.
  • 덩어리 하나의 크기를 재거나, 덩어리 전체를 다른 값으로 바꿉니다. 그림판의 페인트 통으로 칠하듯 이어진 칸을 한 번에 바꾼다고 해서 플러드 필(flood fill)이라고 부릅니다.
  • 문제에 “상하좌우로 인접한”, “연결된”이라는 말이 나옵니다.

덩어리를 세거나 칠하는 데는 DFS와 BFS 모두 쓸 수 있습니다. 다만 “가장 짧은 거리”, “최소 몇 번 만에”를 묻는다면 한 레벨씩 퍼지는 BFS를 씁니다. DFS는 한 방향으로 깊이 들어가며 먼저 닿은 길로 칸을 방문하기 때문에, 그 길이 가장 짧다는 보장이 없습니다.

어떻게 동작하나

무엇을 한 섬으로 보나

LeetCode 200의 예제 2 격자입니다. 1이 땅, 0이 물이고, 칸마다 몇 번째 섬인지 번호를 붙였습니다.

01234 0123 1 섬1 1 섬1 0 0 0 1 섬1 1 섬1 0 0 0 0 0 1 섬2 0 0 0 0 0 1 섬3 1 섬3

상하좌우로 맞닿은 땅만 한 섬입니다. 그래서 왼쪽 위의 네 칸은 섬 1 하나이고, 가운데 (2, 2)는 섬 1의 (1, 1)과 대각선으로만 닿아 있어 따로 섬 2가 됩니다. 오른쪽 아래 두 칸은 좌우로 붙어 있으니 섬 3 하나입니다. 이 격자의 답은 3입니다.

훑다가 땅을 만나면, 이어진 땅을 모두 지운다

섬을 세는 순서는 이렇습니다.

  1. 격자를 왼쪽 위부터 한 칸씩 훑습니다.
  2. 아직 지우지 않은 땅을 만나면 섬 하나를 셉니다.
  3. 그 칸에서 출발해 이어진 땅을 모두 지웁니다.

3번에서 섬 전체를 지워 두기 때문에, 훑기가 같은 섬의 다른 칸에 도착해도 이미 지운 칸이라 다시 세지 않습니다. 지우지 않으면 땅 칸마다 한 번씩 세어 버립니다.

이어진 땅을 지울 때 쓰는 방법이 깊이 우선 탐색(DFS, depth-first search)입니다. 지금 칸을 지운 뒤 상하좌우 이웃 중 땅인 칸으로 들어가고, 거기서도 같은 일을 반복합니다. 한 방향으로 갈 수 있는 데까지 먼저 들어가 보고, 막히면 돌아와 다음 방향을 보는 식이라 재귀 함수로 쓰기 좋습니다. 아직 끝나지 않은 재귀 호출이 쌓인 것을 호출 스택이라고 부릅니다.

칸을 지우는 시점도 중요합니다. 칸에 들어가자마자 지워야, 이웃으로 내려간 호출이 방금 떠나온 칸을 다시 땅으로 보고 되돌아 들어가지 않습니다.

직접 따라가 보기

“다음”을 누르면 한 걸음씩 진행합니다. 2~5번째 단계에서 섬 1이 (0, 0) → (1, 0) → (1, 1) → (0, 1) 순서로 지워지며 호출 화살표가 뻗습니다. 이어서 6번째 단계에서 훑기가 (0, 1)에 도착하는데, 이미 지운 칸이라 세지 않고 지나가는 것을 보세요.

01234 0123 1 섬1 1 섬1 0 0 0 1 섬1 1 섬1 0 0 0 0 0 1 섬2 0 0 0 0 0 1 섬3 1 섬3
변수
result
0
(r, c)
–
호출 스택

왼쪽 위 (0, 0)부터 한 칸씩 훑으며, 지우지 않은 땅을 찾습니다

  • 지금 칸
  • 아직 끝나지 않은 호출
  • 지운 땅
  • 물
LeetCode 200 예제 2(섬 3개). 이웃은 아래·위·오른쪽·왼쪽 순서로 봅니다. 빌드할 때 DFS를 실제로 돌려 기록한 단계입니다.

위쪽에서 “다 둘러본 뒤 표시”를 고르면, 이웃을 다 본 다음에야 칸을 지우는 코드가 실행됩니다. 3번째 단계에서 (1, 0)으로 내려간 뒤, (1, 0)이 위쪽 이웃 (0, 0)을 봅니다. (0, 0)은 아직 지워지지 않았으니 다시 호출하고, 두 칸이 서로를 끝없이 호출합니다.

대표 문제 풀이

LeetCode 200은 '1'(땅)과 '0'(물)로 된 격자 grid에서 섬의 개수를 돌려주는 문제입니다. 격자 바깥은 모두 물로 봅니다.

제가 복습 때 힌트 없이 풀어 LeetCode 채점을 통과한 코드입니다.

var numIslands = function(grid) {
    let result = 0;

    const rows = grid.length;
    const cols = grid[0].length;

    const move = [[1,0],[-1,0],[0,1],[0,-1]]

    function dfs(r,c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
            return;
        }

        grid[r][c] = '0';

        for(const [moveY, moveX] of move) {
            dfs(r+moveY,c+moveX)
        }
    }

    for(let row=0;row<rows;row++) {
        for(let col=0;col<cols;col++) {
            if(grid[row][col] === '1') {
                result++;
                dfs(row, col)
            }
        }
    }

    return result;
};

dfs는 격자 밖이거나 물이면 바로 돌아옵니다. 땅이면 grid[r][c] = '0'으로 그 칸을 물로 바꾸는데, 이것이 “지운다”에 해당합니다. 따로 방문 배열을 두지 않고 입력 격자를 고쳐 방문 표시로 쓴 것입니다. 바깥 이중 반복문이 훑기이고, '1'을 만날 때마다 result를 올린 뒤 dfs로 그 섬을 지웁니다. 이웃을 보는 순서는 move 배열대로 아래·위·오른쪽·왼쪽이고, 위 시각화도 이 순서를 따릅니다.

모든 칸은 훑기에서 한 번, dfs에서 많아야 네 방향으로 한 번씩 확인되므로 시간은 O(행 × 열)입니다. 격자 전체가 한 섬이면 재귀 호출이 칸 수만큼 쌓일 수 있어 공간도 O(행 × 열)입니다.

재귀 없이 스택으로 쓰기

재귀 함수는 아직 끝나지 않은 호출을 호출 스택에 쌓아 두고, 마지막에 쌓은 호출부터 이어 갑니다. 이 일을 배열로 직접 하면 재귀 없이도 같은 깊이 우선 탐색이 됩니다. 배열의 push로 갈 칸을 쌓고, pop으로 가장 최근에 쌓은 칸부터 꺼내 이어 가는 것입니다.

var numIslands = function (grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const move = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let result = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] !== '1') continue;
      result++;

      // 호출 스택 대신 배열을 스택으로 쓴다
      const stack = [[row, col]];
      grid[row][col] = '0';
      while (stack.length > 0) {
        const [r, c] = stack.pop();
        for (const [dr, dc] of move) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== '1') continue;
          grid[nr][nc] = '0'; // 스택에 넣을 때 지운다
          stack.push([nr, nc]);
        }
      }
    }
  }
  return result;
};

여기서는 칸을 스택에 넣을 때 지웁니다. 재귀 풀이에서 “들어가자마자 지운다”와 같은 이유로, 넣을 때 지워야 아직 꺼내지 않은 칸을 다른 이웃이 한 번 더 넣지 않습니다. 이웃을 넣고 꺼내는 순서 때문에 칸을 지우는 순서는 재귀 풀이와 조금 다르지만, 세는 섬의 개수는 같습니다. 무작위 격자 3,000개로 두 풀이의 결과가 같은지 확인했습니다.

격자가 아닌 그래프에서

격자는 “상하좌우 이웃”이 정해진 그래프입니다. 이웃이 간선 목록으로 주어지는 일반 그래프에서도 방법은 같고, 이웃을 찾는 부분과 방문 표시만 바뀝니다. 아래는 노드 n개와 간선 목록 edges를 받아 이어진 덩어리의 개수를 세는 코드입니다.

function countComponents(n, edges) {
  // 노드마다 이웃 목록을 만든다 (인접 리스트)
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const visited = new Set();
  function dfs(node) {
    visited.add(node); // 들어가자마자 표시한다
    for (const next of graph[node]) {
      if (!visited.has(next)) dfs(next);
    }
  }

  let count = 0;
  for (let node = 0; node < n; node++) {
    if (!visited.has(node)) {
      count++;
      dfs(node);
    }
  }
  return count;
}

격자 풀이의 훑기가 노드 번호를 도는 반복문으로, grid[r][c] = '0'이 visited.add(node)로 바뀌었을 뿐 구조는 같습니다. 입력을 고칠 수 없는 그래프에서는 이처럼 방문 표시를 Set이나 배열로 따로 둡니다. 간선 [[0, 1], [1, 2], [3, 4]]와 노드 5개를 넣으면 {0, 1, 2}와 {3, 4} 두 덩어리라 2가 나옵니다.

자주 하는 실수

칸을 다 둘러본 뒤에 표시합니다. 이 문제를 처음 풀 때 저는 “더 이상 탐색이 불가능하면 1을 2 같은 다른 수로 바꾸겠다”고 접근을 설명했습니다. 표시가 탐색이 끝난 뒤로 밀리면, 이웃으로 내려간 호출이 방금 떠나온 칸을 아직 땅으로 보고 되돌아 들어갑니다. 위 시각화의 “다 둘러본 뒤 표시”가 이 경우이고, 칸에 들어가자마자 표시해야 합니다.

재귀가 너무 깊어질 수 있습니다. 처음 풀었을 때의 재귀 풀이도 LeetCode 채점은 통과했지만, 로컬 Node.js(v22)에서 전부 땅인 격자를 돌렸을 때 80×80부터 Maximum call stack size exceeded가 났습니다. 위 풀이도 같은 재귀 구조라 같은 한계가 있습니다. 문제의 최대 크기인 300×300이 전부 땅이면 호출이 90,000번까지 쌓입니다. 이런 입력이 걱정되면 위의 스택 풀이처럼 반복문으로 바꾸거나, 큐로 한 레벨씩 퍼지는 BFS로 바꿉니다. 같은 300×300 격자에서 재귀 풀이는 로컬 Node.js(v23)에서 Maximum call stack size exceeded로 멈췄고, 스택 풀이는 13ms에 1을 돌려줬습니다.