[자바][disjoint set] Leetcode Number of Islands

leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

 

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        UnionFind uf = new UnionFind(grid);
        
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    
                    if (i-1>=0 && grid[i-1][j] == '1') {
                        uf.union(i*n+j, (i-1)*n+j);
                    }
                    if (i+1<m && grid[i+1][j] == '1') {
                        uf.union(i*n+j, (i+1)*n+j);
                    }
                    if (j-1>=0 && grid[i][j-1] == '1') {
                        uf.union(i*n+j, i*n+(j-1));
                    }
                    if (j+1<n && grid[i][j+1] == '1') {
                        uf.union(i*n+j, i*n+(j+1));
                    }
                }
            }
        }
        
        return uf.getCount();
    }
    
    
    
    class UnionFind {
        int[] parent;
        int[] rank;
        int count;
        
        public UnionFind(char[][] grid) {
            
            int m = grid.length;
            int n = grid[0].length;
            count = 0;
            
            parent = new int[m*n];
            rank = new int[m*n];
            
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        parent[i*n+j] = i*n+j;
                    }
                    //rank[i*n+j] = 0;
                }
            }
            
            
        }
        
        public int find(int i) {//path compression
            if (parent[i] != i) {
                parent[i] = find(parent[i]);
            }
            return parent[i];
        }
        
        public void union(int x, int y) {//union by rank
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX != rootY) {//부모가 같으면.. 이미 union
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                count--;
            }
        }
        
        public int getCount() {
            return count;
        }
    }
}