[LeetCode] 827. Making A Large Island

문제 출처: https://leetcode.com/problems/making-a-large-island/

Making A Large Island - LeetCode

 

문제

n x n 사이즈의 행렬 grid가 주어진다. 단 한 개의 0을 1로 바꿀 수 있다.

 

이 과정(0을 1로 바꾸는 과정)을 수행한 후에 grid 내에서 가장 큰 섬의 크기를 반환하라.

 

섬이란, 4방향으로 연결된 1의 그룹을 말한다. 

 

예제

Input: grid = [[1,0],[0,1]]
Output: 3

Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Input: grid = [[1,1],[1,0]]
Output: 4

Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Input: grid = [[1,1],[1,1]]
Output: 4

Explanation: Can't change any 0 to 1, only one island with area = 4.

 

풀이

실제 수행해야 되는 내용을 그림으로 이해하기 위해서 다음의 예를 생각해보자. 

위의 예는 각 구별되는 섬에 색을 칠해놓은 것이다. (1, 1) 지점의 빨간 테두리의 셀은 예시로 1로 변경할 셀에 대해서 표시를 한 것이다. 해당 지점을 1로 변경하게 되면, 상하좌우의 4방향 지점들이 영향을 받게 될 것이다. 그래서 해당 지점으로부터 상하좌우의 4방향을 보면서 섬이 있는지 체크한다. 현재 예의 경우 파란색 섬과 주황색 섬이 인접해있는 것을 알 수 있고, 이 섬을 연결하면 된다. 연결의 경우 간단하다. 파란색 섬의 경우 크기가 4이고, 주황색 섬의 경우 크기가 6이다. 그래서 연결된 섬의 크기는 4 + 6 + 1 = 11 이 된다.

 

위의 예제를 토대로 문제 풀이에 필요한 정보를 다음과 같이 정리할 수 있다.

1. (최초 주어지는 grid 에서) 하나의 섬을 이루는 셀들의 정보
2. (최초 주어지는 grid 에서) 각 섬의 크기

이러한 정보를 얻기 위해서 DFS나 Union-Find 방법 등 여러 방법이 사용될 수 있다. 여기서는 Union-Find 알고리즘을 사용했으며, Union-Find 알고리즘은 서로소 집합 자료구조를 표현할 때 사용하는 알고리즘으로, 위 문제에서는 각 섬이 서로소 집합에 해당한다.

class UnionFind {
    constructor(n) {	// n: grid의 행(또는 열)의 크기
    	this.id = Array(n*n).fill(0).map((val, idx) => idx);
        this.sz = Array(n*n).fill(1);
    }
    
    root(i) {
    	while(this.id[i] != i) {
            this.id[i] = this.id[this.id[i]];
            i = this.id[i]
        }
     	return i;
    }
    
    connected(p, q) {
    	return this.root(p) == this.root(q);
    }
    
    union(p, a) {
    	const i = this.root(p);
        const j = this.root(q);
        
        if ( i == j ) { return; }
        
        if (this.sz[i] > this.sz[j]) { this.id[j] = i; this.sz[i] += this.sz[j]; }
        else			     { this.id[i] = j; this.sz[j] += this.sz[i]; }
    }
}

이 Union-Find를 이용하여 주어지는 grid를 표현하는 것을 코드로 작성해보자.

var largestIsland = function(grid) {
    const N = grid.length;
    const uf = new UnionFind(N);
    
    const zeroPoint = [];
    
    const m = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    
    // grid => UnionFind로 표현
    for (let r = 0; r < N; r++) {
    	for (let c = 0; c < N; c++) {
            if (grid[r][c] == 0) { zeroPoint.push([r, c]); continue; }
            
            const id = r * N + c;
            // 현재 셀의 우측과 하단 셀 확인
            for (let i = 0; i < 2; i++) {
            	const adjRow = r + m[i][0];
                const adjCol = c + m[i][1];
                
                if (adjRow >= N || adjCol >= N || grid[adjRow][adjCol] == 0) { continue; }
                
                const adjCellId = adjRow * N + adjCol;
                uf.uion(id, adjCellId);
            }
        }
    }
}

주어진 grid를 통해서 구별되는 섬을 얻기 위해서, 모든 셀을 최소 한 번씩은 방문하도록 2중 반복문을 사용하였다. 각 셀을 방문할 때마다, 방문한 셀이 1 값을 갖고 있다면 그 셀의 우측과 하단 셀을 체크하여 1이라면 현재 셀과 연결과정을 수행한다. 이와 같은 과정을 통해 구별되는 섬을 얻을 수 있다. 우측과 하단의 셀만 체크하는 것은 같은 지점들을 중복해서 체크하는 과정을 제거하기 위함이다.

 

이 과정을 수행하면서 추가적으로 수행하는 작업은 0인 지점에 대한 좌표를 별도로 저장하는 것이다. 이후 과정에서 0인 지점을 찾기 위해 다시 grid 행렬 전체를 탐색하는 불필요한 과정을 없앨 수 있다.

 

다음으로 수행해야 하는 과정에 대해 생각해보면, 0인 지점들을 방문하면서 1로 변경해보고, 이때 연결되는 섬이 존재하는지 찾아보는 것이다.

var largesetIsland = function(grid) {
	const N = grid.length;
    const uf = new UnionFind(N);
    
    const zeroPoint = [];
    
    const m = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    // Union-Find 과정
    ...
    
    const ans = Math.max(...uf.sz);
    // 연결되는 섬 체크
    for (let [r, c] of zeroPoint) {
    	let connectedSize = 1;
        
        const roots = new Set();
    	for (let i = 0; i < 4; i++) {
            const adjRow = r + m[i][0];
            const adjCol = r + m[i][1];
            
            if (adjRow < 0 || adjRow >= N || adjCol < 0 || adj >= N) { continue; }
            if (grid[adjRow][adjCol] == 0) { continue; }
            
            roots.add(adjRow * N + adjCol);
        }
        
        for (let root of roots) {
        	connectedSize += uf.sz[root];
        }
        
        ans = Math.max(ans, connectedSize);
    }
    
    return ans
}

연결되는 섬을 찾을 때는 4방향 모두 체크해봐야 한다. 또한 체크를 하면서 주의해야할 점이 있는데, 찾아진 섬이 동일한 섬일 경우를 주의해야 한다. 다시 한번 아래 그림을 살펴보자.

 

상단의 셀 중에서 (0, 2) 지점을 보면 좌측에는 파란 섬과 연결되어 있고, 우측과 하단에는 주황 섬과 연결되어 있다. 자칫이 지점에 대해서 잘못 계산하게 되면 주황 섬을 두 번 고려한 결과인 4 + 6 + 6 + 1 = 17 이 된다. 이러한 상황을 회피하고자 집합(set) 자료구조를 사용하여 동일한 섬이 여러 번 고려되지 않도록 코드를 구성하였다.

 

 

Github: 827.js

GitHub - opwe37/Algorithm-Study