[LeetCode] 463. Island Perimeter

문제 출처: https://leetcode.com/problems/island-perimeter/

Island Perimeter - LeetCode

---

문제

지도가 $row \times col$ 크기의 $grid$로 표현되어 주어진다. $grid[i][j] = 1$은 땅을 의미하고 $grid[i][j] = 0$은 물을 의미한다.

 

격자 칸은 상하좌우로 연결되어 있다(대각 연결은 없음). $grid$는 사방이 물로 둘러싸여 있으며, 정확히 한 개의 섬이 있다(섬 = 한 개 또는 그 이상의 땅 칸이 연결되어 있음).

 

섬에는 "호수"가 없다. 즉, 섬으로 둘러 쌓인 물이 없다는 것을 의미한다. 한 칸은 변의 길이가 1인 정사각형이다. 격자는 너비와 높이가 최대 100을 넘지 않는 직사각형이다. 섬의 둘레를 계산하라.

예제

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

Explanation: The perimeter is the 16 yellow stripes in the image above.

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

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

---

풀이

grid에서 땅과 물의 경계 지점의 수를 세는 것으로 섬의 둘레를 계산할 수 있습니다. 경계 지점이라는 것은 칸에 적힌 값이 다른 경우를 말합니다.

위 그림은 예제 1의 입력 grid를 그린 것입니다. 격자 내에 표시되어 있는 화살표는 0 → 1 혹은 1 → 0 으로 바뀌는 지점을 표시한 것입니다. 대부분의 섬 외곽지역에 화살표가 존재합니다. 단, 격자 외곽과 맞닿아 있는 섬의 경계지점에는 화살표가 존재하지 않는다는 점이 눈에 띕니다.

 

이러한 지점까지 잡아내기 위해서 기존 격자보다 상하좌우로 1씩 큰 가상의 격자를 만들어 줄 수 있습니다. 추가된 위치는 모두 물로 표시합니다. 문제에서 격자는 물로 둘러 쌓여있다고 명시되어있기 때문에 이렇게 하더라도 문제는 없습니다.

패딩이 추가된 grid

이와 같이 입력으로 주어지는 격자 주변을 물로 감싸게 되면,  0 → 1 혹은 1 → 0 으로 바뀌는 지점을 모두 찾는 것으로 섬의 둘레를 알 수 있습니다.

var islandPerimeter = function(grid) {
    const row = grid.length;
    const col= grid[0].length;
    
    // 격자 상하좌우에 0 패딩 추가
    const paddedGrid = new Array(row+2).fill(0).map(val => new Array(col+2).fill(0));
    for (let r = 1; r < (row+1); r++) {
        for (let c = 1; c < (col+1); c++) {
            paddedGrid[r][c] = grid[r-1][c-1];
        }
    }
    
    let answer = 0;
    
    for (let r = 1; r < (row+1); r++) {
        let tmp = 0;
        for (let c = 1; c < (col+2); c++) {
            if (paddedGrid[r][c-1] != paddedGrid[r][c]) { tmp += 1; }
        }
        answer += tmp;
    }
    
    for (let c = 1; c < (col+1); c++) {
        let tmp = 0;
        for (let r = 1; r < (row+2); r++) {
            if (paddedGrid[r-1][c] != paddedGrid[r][c]) { tmp += 1; }
        }
        answer += tmp;
    }
    
    return answer;
};

 

Github: 463.js

GitHub - opwe37/Algorithm-Study