← 24주차 · 최종 모의고사와 실전 전략
보통BFSDFS그래프

격자 탐색 + 상태 관리

0과 1로 이루어진 격자 grid가 주어져요. 상하좌우로 이어진 1들이 하나의 섬을 이뤄요. 가장 큰 섬의 칸 수를 반환해요. 섬이 하나도 없으면 0을 반환해요.

모든 칸을 훑되 방문한 칸을 다시 세지 않도록 방문 표시를 관리해요. 아직 방문하지 않은 1을 만나면 거기서 DFS나 BFS로 이어진 1을 모두 세고, 그 크기를 최댓값 후보로 삼아요.

예시

예시 1
입력
grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]]
출력
3
설명
왼쪽 위 섬은 3칸, 오른쪽 아래 섬도 3칸이에요. 가장 큰 값은 3이에요.
예시 2
입력
grid = [[0, 0], [0, 0]]
출력
0

제한 사항

  • 1 ≤ 행, 열 ≤ 1,000
  • 각 칸은 0 또는 1이에요.
방문 배열을 만들고 모든 칸을 훑어요. 방문 안 한 1을 만나면 스택(또는 큐)으로 이어진 1을 방문 표시하며 세어 섬 크기를 구하고, 지금까지의 최댓값과 비교해요.
javascript
function maxIsland(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const DX = [-1, 1, 0, 0];
  const DY = [0, 0, -1, 1];
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let best = 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] !== 1 || seen[i][j]) continue;
      let area = 0;
      const stack = [[i, j]];
      seen[i][j] = true;
      while (stack.length > 0) {
        const [x, y] = stack.pop();
        area++;
        for (let d = 0; d < 4; d++) {
          const nx = x + DX[d];
          const ny = y + DY[d];
          if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) continue;
          if (grid[nx][ny] === 1 && !seen[nx][ny]) {
            seen[nx][ny] = true;
            stack.push([nx, ny]);
          }
        }
      }
      best = Math.max(best, area);
    }
  }
  return best;
}
이전 문제문자열 파싱 + 정렬
다음 문제DP 또는 그리디 판단
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.