[ leetcode 문제풀이 ] Number of Islands

Number of Islands - LeetCode

Number of Islands - LeetCode

(Number of Islands 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

 

< Number of Islands 문제 설명 >

 

Number of Islands 문제는 다음과 같다.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

1(육지)과 0(바다)로 이루어진 지도를 나타내는 주어진 m x n 크기의 2차원 격자 grid에 대해 섬의 수를 리턴하여라.

섬이라는 것은 물로 둘러싸여 있고, 수평 또는 수직으로 인접한 육지를 연결하여 형성된다. grid의 네 모서리가 바다로 둘러싸여 있다고 가정해도 좋다.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 m == grid.length, n == grid[i].length, 1 ≤ m, n ≤ 300, grid[i][j] is '0' or '1' 이다. 

 

 

 

 

---

< Number of Islands 문제 접근 >

 

섬의 개수를 세라는 것은 grid라는 집합을 몇 개의 서로소 집합(disjoint-set)으로 나눌 수 있겠는가와 같은 말이다. 그러므로 집합의 분할을 위해 사용되는 Disjoint-set data structure(Union Find data structure)을 이용하였다.

 

우선 작성한 코드를 보면 다음과 같다. (Cpp 사용)

 

#include <unordered_map>
using namespace std;

struct Node{
    Node* parent;
    int rank = 0;
};
    
// this can be decreased to a constant amount memory
// by performing both passes in the same direction
// two passes - once to find the root, once to update pointers.
Node* Find(Node* x){
    Node* root = x;
    while(root->parent != root)
        root = root->parent;
     
    while(x->parent != root){
        Node* parent = x->parent;
        x->parent = root;
        x = parent;
    }
    return root;
}
    
// union by rank - ensure that trees do not become too deep
void Union(Node* x, Node* y){
    x = Find(x);
    y = Find(y);
        
    if(x == y) return;
      
    if(x->rank < y->rank){
        Node* temp = y;
        y = x;
        x = temp;
    }
        
    y->parent = x;
    if(x->rank == y->rank)
        x->rank += 1;
}     
    
int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
      
    Node** GridNode = new struct Node*[m];  // (1)
    for(int i=0;i<m;i++)
        GridNode[i] = new struct Node[n];
    
    // (2) MakeSet Func.    
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            GridNode[i][j].parent = GridNode[i] + j;
        
    // (3) connect island (by Union Func.)
    for(int i=0;i<m;i++)
        for(int j=0;j<n-1;j++)
            if(grid[i][j] == '1' && grid[i][j+1] == '1')
                Union(GridNode[i]+j, GridNode[i]+j+1);
      
    for(int i=0;i<m-1;i++)
        for(int j=0;j<n;j++)
            if(grid[i][j] == '1' && grid[i+1][j] == '1')
                Union(GridNode[i]+j, GridNode[i+1]+j);
        
    // (4)
    unordered_map<Node*, int> ans;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            if(grid[i][j] == '1')
                ans[Find(GridNode[i]+j)]++;
      
    return ans.size();
} // runtime: 39 ms (faster than 68.50 %), memory usage: 16 MB (less than 23.81 %)

 

전반적인 코드의 흐름을 설명하면

(1) 주어진 grid 배열에 대해 각각의 cell(grid[i][j])을 Node라는 구조체(parent: cell이 속한 집합의 root Node를 가리키는 포인터, rank: root Node에 대해 집합의 깊이를 나타냄)로 만들기 위해 메모리를 할당한다.

(2) 각각의 cell의 Node 구조체의 parent를 자기 자신으로 초기화한다. 이는 곧 자기 자신을 root Node로 하는 집합이라는 것이고, grid의 모든 cell은 서로 다른 집합으로 간주할 수 있다.

(3) 첫 번째 반복문은 grid의 가로 방향에 대해, 두 번째 반복문은 grid의 세로 방향에 대해 인접한 cell이 모두 육지이면('1'의 값을 가지면) Union operation을 실시한다. 
(Union 함수는 서로 다른 집합을 합치는 역할을 한다. Find 함수를 통해 찾은 두 cell의 root Node가 같으면 이미 같은 집합이므로 여기서 실행을 종료하고, 그렇지 않은 경우 rank가 낮은 집합의 root Node의 parent를 rank가 높은 집합의 root Node가 가리키도록 해 두 집합을 합친다.)

(4) grid의 육지 cell(grid[i][j] == '1')에 대해 이들의 root Node를 조사하고 Hash Table의 (key, value)로 카운트한다. 이렇게 카운트한 root Node의 종류(ans.size())가 number of Islands를 나타내게 되는 것이다.

 

 

알고리즘의 성능을 봤을 때 좋은 runtime을 나타냈으나, hash table을 사용해서 그런지 memory usage에서는 약간 아쉬운 결과를 나타낸 것 같다.

 

 

**여담**

(4)에서 ans[Find(GridNode[i]+j)]++ operation으로 얻어낸 ans Hash Table의 value는 key에 해당하는 Node와 연결된 육지의 개수(grid[i][j] == '1'의 개수)가 될 것이다. 따라서, ans Hash Table을 탐색해 value의 최댓값을 찾아내 리턴하도록 하면 Max Area of Island - LeetCode 문제에서 요구하는 답을 구할 수 있을 것이다.