[LeetCode][JAVA] 200. Number of Islands

💡 문제

200. Number of Islands

 (https://leetcode.com/problems/number-of-islands/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

 

• 그래프 관점의 격자(Grid as Graph): 각 칸을 정점으로 보고, 상하좌우 4방향으로 간선이 있다고 보면 연결된 ‘1’들의 묶음이 곧 섬이다.
• BFS/DFS로 영역(Connected Component) 세기: 방문하지 않은 육지(‘1’)를 발견할 때마다 탐색을 시작해 연결된 모든 칸을 방문 처리하고, 시작 횟수가 섬의 개수다.
• 방문 처리 방식: visited 배열을 별도로 쓰거나, 입력 그리드를 직접 수정(‘1’→‘0’) 하여 재방문을 방지한다.

 

---

🤓 문제 풀이

그리드를 순회하며 ‘1’을 만나면 섬 카운트를 1 증가시키고, BFS로 연결된 모든 ‘1’을 큐로 확장하며 ‘0’으로 바꾸어 방문처리한다.
모든 칸을 한 번씩만 방문하므로 시간은 O(mn)이다.

🔨 문제 설명

• 입력: m x n 크기의 2D 문자 배열 grid ('1'=땅, '0'=물)
• 출력: 섬의 개수(상하좌우 4방향으로 연결된 ‘1’들의 묶음 수)
• 제약: 1 <= m, n <= 300, 각 원소는 '0' 또는 '1'

예)

• [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] → 1
• [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] → 3

---

🔨 접근 방법

1. 이중 루프로 모든 좌표 (r,c)를 순회.
2. grid[r][c] == '1'이면 섬 시작점:
   • 섬 개수 ans++
   • BFS 큐에 넣고, 팝하면서 4방향 이웃 중 '1'을 발견하면 '0'으로 바꾸고 큐에 추가.
3. 전 그리드를 처리하면 ans가 정답.

방문 처리를 즉시 ‘0’으로 변경하면 중복 큐 삽입과 재방문을 방지할 수 있다.

---

🔨 문제 풀이 과정

 

• 외부 루프에서 새 섬 시작점을 발견 → BFS 호출
• BFS는 시작점을 큐에 넣고, 큐가 빌 때까지 이웃 확장
• 이웃 좌표가 범위 내이고 값이 **‘1’**이면 ‘0’으로 전환 후 큐에 삽입
• BFS가 끝나면 해당 시작점과 연결된 모든 육지가 처리 완료

 

 

---

🔨 구현코드

package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. Number of Islands
 * 그리드 BFS/DFS 기반 영역 탐색
 * https://leetcode.com/problems/number-of-islands/description/
 *
 * '1'(토지)과 '0'(물)의 지도를 나타내는 m x n 2D 이진 그리드 그리드가 주어지면, 섬의 수를 반환
 * 섬은 물로 둘러싸여 있으며 인접한 땅을 수평 또는 수직으로 연결하여 형성
 * 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정
 *
 * 예 1:
 * 입력: 그리드 = [
 * ["1","1","1","1","0"],
 * ["1","1","0","1","0"],
 * ["1","1","0","0","0"],
 * ["0","0","0","0","0"]
 * ]
 * 출력: 1
 *
 * 예제 2:
 * 입력: 그리드 = [
 * ["1","1","0","0","0"],
 * ["1","1","0","0","0"],
 * ["0","0","1","0","0"],
 * ["0","0","0","1","1"]
 * ]
 * 출력: 3
 *
 * 제약 조건:
 * m == 격자.길이
 * n == 격자[i] 길이
 * 1 <= m, n <= 300
 * grid[i][j] is '0' or '1'
 */
public class LeSolution08BFS {
    private int m, n;
    private char[][] g;
    private static final int[] DR = {1, -1, 0, 0};
    private static final int[] DF = {0, 0, 1, -1};

    public int numIslands(char[][] grid) {
        g = grid;
        m = g.length;
        n = g[0].length;

        int ans = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (g[r][c] == '1') {
                    ans++;
                    bfs(r, c);
                }
            }
        }
        return ans;
    }

    private void bfs(int sr, int sc) {
        Queue<int[]> q = new LinkedList<>();
        g[sr][sc] = '0';
        q.offer(new int[]{sr, sc});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];

            for (int k = 0; k < 4; k++) {
                int nr = r + DR[k];
                int nc = c + DF[k];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && g[nr][nc] == '1') {
                    g[nr][nc] = '0';
                    q.offer(new int[]{nr, nc});
                }
            }
        }
    }

    public static void main(String[] args) {
        LeSolution08BFS sol = new LeSolution08BFS();
        System.out.println(sol.numIslands(new char[][]{{'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}}));
        System.out.println(sol.numIslands(new char[][]{{'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}}));
    }
}

---

📚 풀이 보완

코드 설명 (핵심 라인)

• if (g[r][c] == '1') { ans++; bfs(r, c); }
  → 새로운 섬을 발견할 때마다 BFS로 연결된 모든 육지를 한 번에 방문 처리.
• g[nr][nc] = '0'
  → 방문 즉시 물로 바꿔 중복 방문을 차단(별도의 visited 불필요).
• DR/DC
  → 4방향 오프셋을 배열로 관리하여 반복문으로 이웃 계산을 단순화.
• 방문 처리 시점을 큐에 넣을 때가 아니라 큐에서 뺄 때 하는 경우 → 동일 노드가 중복 삽입될 수 있다.
  → 큐에 넣기 직전에 방문 처리(‘0’ 변경)하자.
• 대각 연결(8방향)로 착각 → 이 문제는 4방향만 연결이다.
• 입력을 직접 수정하기 어렵다면 별도의 visited[m][n] 사용(메모리 여유 확인 필요).

---

📍 Plus+

 

• DFS 버전: 재귀/스택으로 동일하게 구현 가능. 단, Java에서 최악 mn 깊이 재귀는 스택오버플로 가능성 → BFS가 안전한 편.
• Union-Find(DSU): 모든 ‘1’을 노드로 보고 인접한 ‘1’끼리 union, 마지막에 루트 개수 세기. 구현은 복잡하지만 개념적으로 동일.
• 다른 변형: 8방향 연결, 여러 문자 타입(‘2’, ‘3’…), 섬의 최대 면적/둘레 문제 등도 동일한 패턴으로 해결 가능.

 

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도

• O(mn) : 각 칸을 최대 한 번씩 방문/큐 삽입

공간 복잡도

• O(mn) : 최악의 경우(전부 ‘1’) 큐에 많은 칸이 들어갈 수 있음
  (별도 visited를 쓰지 않으므로 추가 배열은 사용하지 않음)

• 전략: 격자를 그래프로 보고, ‘1’을 시작점으로 BFS를 수행해 연결된 영역을 한 번에 지운다.
• 핵심: 큐에 넣을 때 바로 방문 처리(‘1’→‘0’).
• 복잡도: 시간 O(mn), 공간 O(mn)(최악 큐 크기).

---

풀이 참고 로직

 

• 외부 순회로 시작점 찾기: if (grid[r][c] == '1') { ans++; bfs(r,c); }
• BFS 확장: 상하좌우 4방향, 범위체크 후 '1'이면 '0'으로 바꾸고 큐 삽입
• 방문 처리를 즉시 수행해 중복 삽입 방지