[2024] day 110. Leetcode 463. Island Perimeter

gunny·2024년 4월 18일

leetcode 463. Island Perimeter leetcode 463. Island Perimeter python

코딩테스트

목록 보기

423/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 18일 (목)
Leetcode daily problem

463. Island Perimeter

https://leetcode.com/problems/island-perimeter/?envType=daily-question&envId=2024-04-18

Problem

grid[i][j] = 1은 토지를 나타내고, grid[i][j] = 0은 물을 나타내는 지도를 나타내는 행 x 열 grid가 제공된다.
그리드 셀은 수평/수직(대각선이 아님)으로 연결됩니다. 그리드는 물로 완전히 둘러싸여 있으며 정확히 하나의 섬(즉, 하나 이상의 연결된 육지 셀)이 있다.

섬에는 "호수"가 없는데, 이는 내부의 물이 섬 주변의 물과 연결되어 있지 않음을 의미한다. 한 셀은 변의 길이가 1인 정사각형입니다. 그리드는 직사각형이고 너비와 높이가 100을 초과하지 않을 때, 섬의 둘레를 반환한다.

즉, 2차원의 행렬에서 섬의 둘레를 계산한다.

Solution

greedy

섬의 둘레는 각 1이 땅과 물의 경계에 있을 때마다 4의 길이를 더한다.
만약 1이 다른 1과 인접해있따면 둘레에서 2의 길이가 감소된다.
왜냐하면 두 개의 1이 인접하면 서로를 공유하는 부분의 둘레가 중복되기 때문이다.

그래서 격자를 순회하면서 각 1에 대해 다음 로직을 수행하는데,
주변의 0의 개수를 세어서 둘레에 추가하고, 주변의 1의 개수를 세서 둘레를 감소시키고 최종 업데이트된 둘레를 반환하면 된다.

가장 최적의 선택을 하는 방식으로 문제를 해결하는 그리디 알고리즘을 사용한다.

Code

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        ans = 0
        ROWS, COLS = len(grid), len(grid[0])
        
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    ans += 4
                    if r > 0 and grid[r-1][c] == 1:
                        ans -= 2
                    if c > 0 and grid[r][c-1] == 1:
                        ans -= 2
                        
        return ans