1568. Minimum Number of Days to Disconnect Island

Minimum Number of Days to Disconnect Island

아이디어 자체를 생각해내는 것은 어렵지 않은데, 그 아이디어를 코드로 옮기는 건 어려운 문제였다.

결국 다른 사람의 코드를 보고 풀었다.

해당 문제의 기본 아이디어는 다음과 같다.

- Island가 0이거나 2이상이면 더이상 계산할 필요가 없다.

- 어떠한 경우에도 2이상의 삭제는 불필요 하다.

최악의 경우 [[1,1,1],[1,1,1]] 이라고 해도 (0,0)의 1은 우측 및 하단을 자르면 Island는 2개로 나누어 진다.

[1,1] 이렇게 하나의 island로 나와서 결국 2개를 다 삭제 해야 한다고 해도 최대 2개이다.

[1,1,1] 이 이상의 경우는 가운데 한개를 삭제 하는 것으로 마무리 된다.

결국 답은 2이상을 넘지 못한다.

그럼으로 한개를 삭제하는 것으로 만족하는를 확인 하는게 중요하다.

전 grid를 돌면서 Island하나씩 삭제하고 island가 2개로 갈라지는지 확인 하는 것으로 끝이다.

해당 코드는 타잔 알고리즘으로도 가능하다.

시간 복잡도는

- 최초 Island search하는데 O(grid size)

- 전 grid를 돌면서 island 삭제 하는데 grid size * island가 몇개인지 확인 하는데 grid size가 필요 하다. O(grid size^2)

그러나 cell이 4방향으로 dfs하는 것을 생각 한다면 O(grid size^4) 까지 생각해 볼 수 있다. 

- Space Complexity는 dp 하나만 만들고 삭제하는 방식이라 O(n)이면 된다.

var minDays = function(grid) {
  
    let initIsland = getNumIsland(grid);
    
    if(initIsland == 0 || initIsland == 2) return 0;
    
    for(let i = 0; i < grid.length ; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] == 1) {
                if(getNumIsland(grid,i,j) != 1) return 1;
            }
        }
    }
    
    return 2;
    
    function getNumIsland(grid,row=-1,col=-1){
        let count = 0;
        let dp = new Array(grid.length).fill(0).map(()=>new Array(grid[0].length).fill(0));

        if(0 <= row) dp[row][col] = 1;
        
        for(let i = 0; i < grid.length ; i++){
            for(let j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1 && 0 == dp[i][j]){
                    count++;
                    if(1 < count) return 2;
                    journeyIsland(i,j,dp);
                }
            }
        }

        return count;
    }

    function journeyIsland(row, col, dp){
        if(row < 0 || dp.length <= row || col < 0 || dp[0].length <= col) return;
        if(!(grid[row][col] == 1 && dp[row][col] == 0)) return;

        dp[row][col] = 1;
        journeyIsland(row - 1, col, dp);
        journeyIsland(row + 1, col, dp);
        journeyIsland(row, col - 1, dp);
        journeyIsland(row, col + 1, dp); 
    }
};

 

타잔 알고리즘으로 풀었다. 속도와 Memory 사용이 많이 줄었다.

상기 알고리즘은 모든 island cell에 대해서 island 갯수를 계산 했다면, 타잔은 단 한번만 island cell을 순회 하고 끝낸다.

코드상으로는 for문내에 dfs를 쓴것으로 보이나 그렇지 않다 for문은 island cell을 찾으면 그 이상 순회 하지 않는다

O(grid length), space O(N)

var minDays = function(grid) {
    let cellsCount = 0;
    let bridge = new Array();
    
    let initIsland = getNumIsland(grid);
    
    if(initIsland == 0 || initIsland == 2) return 0;
    if(cellsCount == 2) return 2;
        
    let dp = new Array(grid.length).fill(0).map(()=>new Array(grid[0].length).fill(0));
    
    for(let i = 0; i < grid.length ; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] == 1) {
                tarjan(grid,i,j,dp,1);
                break;
            }
        }
    }
    

    if(0 < bridge.length) return 1;
    
    return 2;
    
    function tarjan(grid,row,col,dp,count,dir=-1){
        
        if(0 < dp[row][col]) return dp[row][col];
        
        dp[row][col] = count;
        
        let min = Number.MAX_VALUE;
        
        if(col + 1 < grid[0].length && grid[row][col+1] == 1 && dir != 1) {
            min = Math.min(min, tarjan(grid, row,col + 1,dp,count+1,3));
        }
        if(row + 1 < grid.length && grid[row+1][col] == 1 && dir != 0) {
            min = Math.min(min, tarjan(grid, row+1,col,dp,count+1,2));
        }
        if(0 <= col - 1 && grid[row][col-1] == 1 && dir != 3) {
            min = Math.min(min, tarjan(grid, row,col - 1,dp,count+1,1));
        }
        if(0 <= row - 1 && grid[row-1][col] == 1 && dir != 2) {
            min = Math.min(min, tarjan(grid, row-1,col,dp,count+1,0));
        }
        if(count < min) bridge.push([row,col]);
        else dp[row][col] = min;
        
        return Math.min(count, min);
    }
    
    function getNumIsland(grid,row=-1,col=-1){
        let count = 0;
        let dp = new Array(grid.length).fill(0).map(()=>new Array(grid[0].length).fill(0));

        if(0 <= row) dp[row][col] = 1;
        
        for(let i = 0; i < grid.length ; i++){
            for(let j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1) cellsCount++;
                if(grid[i][j] == 1 && 0 == dp[i][j]){
                    count++;
                    if(1 < count) return 2;
                    journeyIsland(i,j,dp);
                }
            }
        }

        return count;
    }

    function journeyIsland(row, col, dp){
        if(row < 0 || dp.length <= row || col < 0 || dp[0].length <= col) return;
        if(!(grid[row][col] == 1 && dp[row][col] == 0)) return;

        dp[row][col] = 1;
        journeyIsland(row - 1, col, dp);
        journeyIsland(row + 1, col, dp);
        journeyIsland(row, col - 1, dp);
        journeyIsland(row, col + 1, dp); 
    }
};