Written by DK-Lite
on December 07, 2019

[LeetCode .200] Number of Islands

Number of Islands

Problem

주어진 2차 평면에서 섬의 갯수를 출력하는 문제

Solution

BFS를 이용한 플러드필 방식을 이용할수 있지만 해당 포스트에서는 Union-Find 방법을 이용해보겠다.

2차원 평면을 순회
가로, 세로 위치한 좌표들을 Union 시킴
최종적으로 부모 좌표들만 카운팅

Code

class Solution {
public:
    vector<int> parent;
    int find(int p) {
        if (parent[p] == p) return p;
        return parent[p] = find(parent[p]);
    }
    void uni(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return;
        parent[pb] = pa;
    }
    int numIslands(vector<vector<char>>& grid) {
        
        if(grid.empty()) return 0;
        
        parent.resize(grid.size() * grid[0].size(), 0);        
        int w = grid[0].size();
        
        for(int i = 0 ;i < parent.size(); i++) parent[i] = i;
        for (int y = 0; y < grid.size(); y++) {
            for (int x = 0; x < grid[0].size(); x++) {
                if(grid[y][x] == '0') continue;
                if(y - 1 >= 0 && grid[y-1][x]=='1') uni(y*w + x, (y - 1)*w + x);
                if(x - 1 >= 0 && grid[y][x-1]=='1') uni(y*w + x, y*w + (x - 1));
            }
        }
        int result = 0 ;
        for(int i = 0 ;i < parent.size(); i++) 
            if(parent[i] == i && grid[i/w][i%w]=='1' ) result++;
        
        return result;
    }
};

Reference

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

← → Top