← 15주차 · 그래프와 DFS · BFS
보통그래프BFS/DFS

섬의 개수

1(땅)과 0(물)로 이루어진 2차원 배열 grid가 주어져요. 섬의 개수를 반환해요.

섬은 상하좌우로 인접한 땅끼리 이어진 덩어리예요. 대각선으로는 이어지지 않아요. 격자의 바깥은 모두 물로 둘러싸여 있다고 생각해요.

예시

예시 1
입력
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
출력
3
설명
좌상단 덩어리, 가운데 한 칸, 우하단 두 칸으로 총 3개예요.
예시 2
입력
grid = [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]
출력
1

제한 사항

  • 1 ≤ grid.length, grid[i].length ≤ 300
  • grid[i][j]는 0 또는 1이에요.
격자를 훑다가 아직 방문하지 않은 1을 만나면 섬 개수를 1 늘리고, 거기서 BFS나 DFS로 이어진 땅을 전부 방문 처리해요.
javascript
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let count = 0;
​
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== 1 || seen[r][c]) continue;
      count++;
      const stack = [[r, c]];
      seen[r][c] = true;
      while (stack.length) {
        const [y, x] = stack.pop();
        for (const [dy, dx] of dirs) {
          const ny = y + dy;
          const nx = x + dx;
          if (ny < 0 || ny >= rows || nx < 0 || nx >= cols) continue;
          if (seen[ny][nx] || grid[ny][nx] !== 1) continue;
          seen[ny][nx] = true;
          stack.push([ny, nx]);
        }
      }
    }
  }
  return count;
}
이전 문제연결 요소의 개수
다음 문제이분 그래프 판별
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.