[leetcode / 200] Number of Islands

in Problem Solving on leetcode


날짜: 2021년 8월 30일
카테고리: 그래프
태그: Medium, 200, 파이썬

leetcode 200 - Number of Islands

입출력 예시

예제 입력예제 출력
grid = [[“1”,”1”,”1”,”1”,”0”],[“1”,”1”,”0”,”1”,”0”],[“1”,”1”,”0”,”0”,”0”],[“0”,”0”,”0”,”0”,”0”]]1
grid = [[“1”,”1”,”0”,”0”,”0”],[“1”,”1”,”0”,”0”,”0”],[“0”,”0”,”1”,”0”,”0”],[“0”,”0”,”0”,”1”,”1”]]3

코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i,j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
                return
            grid[i][j] = 0
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
            
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
                    
        return count
파이썬 알고리즘 인터뷰 12-1

풀이 과정

함수 내에 dfs함수 전체를 중첩 함수로 생성
i나 j가 전체 지도 범위 밖으로 벗어나거나, 1이 아닌 수가 된다면(섬이 끝나는 부분) return 해버리는 함수 dfs를
동서남북 사방으로 체크

이중 반복으로 이차원 배열의 모든 원소를 탐색
if grid[i][j] == '1': 구문을 통해 백트래킹의 성향을 띔

하나의 섬을 모두 탐색한 후 count에 1을 더함

모든 반복이 끝났을 때 count 반환

반성



© 2021. by hminkim