[LeetCode] 463. Island Perimeter (Daily Question)

문제

---

 

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.

 

바다를 의미하는 0과 섬의 땅을 의미하는 1로 구성된 2차원 배열 grid가 주어졌을 때, 섬 해안선의 길이를 구하는 문제이다.

 

Example 1:

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.

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

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

 

풀이

---

아이디어

좌상단(0, 0)부터 우하단까지 2중 for문으로 탐색하며 특정 조건을 만족하면 (해안선 길이++) 를 한다.

 

조건

1. 현재 좌표가 섬인 경우

2. 근처(상하좌우)좌표가 존재하지 않거나 바다인 경우

 

코드

class Solution:
    answer = 0

    # 주변 좌표 확인
    def check(self, x, y):
        if x-1 < 0 or not self.grid[x-1][y]: self.answer += 1
        if x+1 >= len(self.grid) or not self.grid[x+1][y]: self.answer += 1
        if y-1 < 0 or not self.grid[x][y-1]: self.answer += 1
        if y+1 >= len(self.grid[0]) or not self.grid[x][y+1]: self.answer += 1 


    def islandPerimeter(self, grid: List[List[int]]) -> int:
        self.grid = grid
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]: self.check(i, j)

        return self.answer

---

 

후기

---

난이도

전반적으로 쉬운 문제였다.

섬이 하나이고 grid의 크기가 작아 2중 for문이라는 쉬운 방법으로 풀 수 있었다.

 

다른 풀이

DFS나 BFS로 섬 내부를 탐색할 수 있다.