박종훈 알고리즘 블로그

(Leetcode) 200 - Number of Islands

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


https://leetcode.com/problems/number-of-islands/description/

그래프 문제로 분류되어 있는데 배열문제에 가깝지 않나 싶다. (실제로 토픽도 배열로 정리되어 있다.)

2차원 배열(grid)에서 1인 부분을 찾았을 때, 주변 영역을 0으로 만들어서 중복 카운트를 하도록 하는 컨셉이 재밌었다.

class Solution {
    int w;
    int h;

    public int numIslands(char[][] grid) {
        int count = 0;
        w = grid.length;
        h = grid[0].length;

        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i,j);
                    count++;
                }
            }
        }

        return count;
    }

    public void dfs(char[][] grid, int i, int j) {
        if(i < 0 || i >= w || j < 0 || j >= h || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0';

        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
    }
}