[LeetCode] 463. Island Perimeter

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

LeetCode - Island Perimeter

문제 유형 : 행렬

문제 난이도 : Easy

 

문제

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

 

row x col의 grid가 있습니다. grid[i][j] == 1이면 땅, grid[i][j] == 0이면, 물입니다.

이 격자의 셀들은 수직/수평으로 연결되어있습니다. 이 격자에는 단 하나의 섬이 물에게 둘러싸여 있습니다.

섬 안에 물이 가둬져 있는 경우는 없습니다. 격자 한 칸의 길이는 1입니다. 너비와 높이가 100을 넘지 않습니다.

섬의 둘레를 구하시오.

 

풀이

단순하게, 각 육지 땅의 칸별로 상하좌우에 인접한 땅이 얼마인지, 물이 얼마인지를 알아내면 된다.

각 육지 땅은 적어도 0개부터 최대 4개까지 인접한 물의 면 수를 가질 수 있다.

인접한 한 칸씩 검사하면서 인접한 물의 면 수를 구해서 누적하면 된다.

 

코드

C++

class Solution {
private:
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int ans = 0;
        int rows = grid.size();
        int cols = grid[0].size();

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; ++k) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == 0) {
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

 

 

Go

func islandPerimeter(grid [][]int) int {
    ans := 0
    rows, cols := len(grid), len(grid[0])

    dx := []int{1, -1, 0, 0}
    dy := []int{0, 0, 1, -1}

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == 1 {
                for k := 0; k < 4; k++ {
                    nx, ny := i+dx[k], j+dy[k]

                    if nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == 0 {
                        ans++
                    }
                }
            }
        }
    }

    return ans
}