[LeetCode] 463. Island Perimeter

접근

• 각 사이드를 확인하여 perimeter를 추가해야 하는 지 그렇지 않은 지를 논리적으로 확실하게  구분하는 것이 핵심
• 문제 조건 중 섬의 갯수는 무조건 하나이므로 DFS나 DFS를 사용하여 탐색 성능을 높이는 것이 중요해 보임
• 논리적 흐름이 잘못되었으면 동일한 코드를 수정하기 보다 논리적 흐름을 재설정하여 코드를 새롭게 짜는 것이 좋은 습관인 것 같음..

 

문제 링크

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

 

솔루션

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        perimeter = 0
        ROW_length = len(grid)
        COL_length = len(grid[0])
        visited = [[False for _ in range(COL_length)] for _ in range(ROW_length)]
        

        def dfs(ROW, COL):
            nonlocal perimeter
            visited[ROW][COL] = True

            # check left side
            if COL == 0 or \
                (COL > 0 and grid[ROW][COL-1] == 0):
                perimeter += 1
            elif (COL > 0 and grid[ROW][COL-1] == 1) and \
                visited[ROW][COL-1] == False:
                dfs(ROW, COL-1)
            
            # check up side
            if ROW == 0 or \
                (ROW > 0 and grid[ROW-1][COL] == 0):
                perimeter += 1
            elif (ROW > 0 and grid[ROW-1][COL] == 1) and \
                visited[ROW-1][COL] == False:
                dfs(ROW-1, COL)
                
            # check right side
            if COL == COL_length-1 or \
                (COL < COL_length-1 and grid[ROW][COL+1] == 0):
                perimeter += 1
            elif (COL < COL_length-1 and grid[ROW][COL+1] == 1) and \
                visited[ROW][COL+1] == False:
                dfs(ROW, COL+1)
            
            # check down side
            if ROW == ROW_length-1 or \
                (ROW < ROW_length-1 and grid[ROW+1][COL] == 0):
                perimeter += 1
            elif (ROW < ROW_length-1 and grid[ROW+1][COL] == 1) and \
                visited[ROW+1][COL] == False:
                dfs(ROW+1, COL)
        
        for r in range(ROW_length):
            for c in range(COL_length):
                if grid[r][c] == 1:
                    dfs(r, c)
                    return perimeter