[LeetCode] 463. Island Perimeter

https://leetcode.com/problems/island-perimeter/

Island Perimeter - LeetCode

Island Perimeter

 

오랜만에 Leetcode..

문제를 푸는건 매일 할 수 있어도 글을 작성하는게 더 힘들다.

글 작성이 힘들땐 코드와 간단한 설명만 올려야겠다.

내가 매일 푸는게 중요하므로..

 

정해진 row, col로 이루어진 그리드안에 중간에 빈 곳이 없는 도형이 있다.

이 도형을 '섬'이라고 하고, 그리드 한 변의 길이를 1이라 할 때, 이 섬의 둘레를 구하는 문제다.

간단한 문제다.

row, col을 차례로 훑어주면 왼쪽에서 오른쪽으로, 위에서 아래로 훑어지는데

이 때, 현재 그리드와 맞닿은 그리드가 섬인지 아닌지(0:섬X, 1:섬)를 판별하면 된다.

예를 들어,

0	0
0	1

일 경우, 1에 해당하는 섬의 둘레는 4가 될 것이다

=>

0	0
0	4

(각 그리드까지 도달했을때의 총 둘레)

 

0	0
1	1

이 경우에는 (1,0) 까지 훑을때는 섬의 둘레는 4가 될 것이고,

(1,1)까지 훑을때는 (1,0)과 인접한 부분은 빼주고 나머지 세 변을 더해주면 된다.

즉, 4 - 1 + 3 = 6이 된다.

=>

0	0
4	6

 

0	1
1	1

마지막으로 이 경우에는 (0,1)은 4,

(1,0)도 닿은 부분이 없으므로 4+4 = 8

(1,1)은 두 변이 닿으므로 2를 빼주고 나머지 두 변이 더해지므로 8 - 2 + 2 = 8 이 된다.

0	4
8	8

 

즉, 총 세가지 경우가 있는데,

1. 인접한 섬이 없을 경우 => +4

2. 인접한 섬이 하나일 경우 => -1 + 3 = +2

3. 인접한 섬이 두개일 경우 => -2 + 2 = +0

로 나누어 훑어주면 된다.

 

아래는 전체 코드이다.

 

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int sum = 0;
        int plus[3] = {4,2,0};
        for (int i=0; i<grid.size(); i++) {
            for (int j=0; j<grid[i].size(); j++) {
                int neighbor = 0;
                if (grid[i][j] == 1) {
                    if (i>0 && grid[i-1][j] == 1) neighbor++;
                    if (j>0 && grid[i][j-1]==1) neighbor++;
                    sum += plus[neighbor];
                }
            }
        }
        return sum;
    }
};