[2024] day 111. Leetcode 200. Number of Islands

gunny·2024년 4월 24일

leetcode 200. Number of Islands leetcode 200. Number of Islands python

코딩테스트

목록 보기

424/530

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

2024년 4월 19일 (금)
Leetcode daily problem

200. Number of Islands

https://leetcode.com/problems/number-of-islands/?envType=daily-question&envId=2024-04-19

Problem

'1'(땅)과 '0'(물)의 지도를 나타내는 m x n 2D 이진 그리드 그리드가 주어지면 섬의 수를 반환한다.

섬은 물로 둘러싸여 있으며 인접한 육지가 수평 또는 수직으로 연결되어 형성된다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정한다.

Solution

Graph serach (DFS or BFS)

해당 문제는 그래프 탐색의 대표적인 문제이다. 주어진 모든 그리드를 순회하면서 육지를 발견할 때마다 해당 육지와 연결된 모든 육지를 방문하며 탐색하는 방법을 사용한다.

해당 문제를 DFS(depth-first search)로 풀어본다면,
모든 그리드를 순회하면서 육지를 발견하면 해당 육지와 연결된 모든 육지를 방문하고, 방문한 육지는 '0'으로 표시하여 중복 방문을 방지합니다. 그리드의 상하좌우를 확인하면서 육지인 경우 해당 육지와 연결된 모든 육지를 방문한다. 최종적으로 방문한 육지의 개수를 섬의 수로 반환한다.

Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        ans = 0
        visited = set()
        ROWS, COLS = len(grid), len(grid[0])
        
        
        def dfs(r,c):
            if r <0 or c<0 or r==ROWS or c==COLS or grid[r][c] == '0' or (r,c) in visited:
                return
            
            visited.add((r,c))
            dfs(r-1, c)
            dfs(r+1, c)
            dfs(r, c-1)
            dfs(r, c+1)
            
            
            
        
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == '1' and (r,c)  not in visited:
                    ans +=1
                    dfs(r,c)
                    
        return ans