[LeetCode] 200. Number of Islands (그래프)

문제

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

"1"이 땅이고, "0"이 바다이다. 섬은 "1"로 이루어지고, "0"에 둘러싸여 있다.

섬의 개수를 구하자.

 

DFS 풀이

 

몇 년 전에 그래프 열심히 풀었었던 기억을 되살려 풀어보았다. 내가 알고 있는 풀이와 책의 풀이가 좀 다르다. 

DFS 버전과 BFS 버전을 만들었다.

 

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        check = [[0]*m for _ in range(n)]
        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
        
        def dfs(x, y):
            check[x][y] = 1
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and not check[nx][ny] and grid[nx][ny] == "1":
                    dfs(nx, ny)
        
        def bfs(x, y):
            q = deque()
            q.append((x, y))
            check[x][y] = 1
            while q:
                x, y = q.popleft()
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < n and 0 <= ny < m and not check[nx][ny] and grid[nx][ny] == "1":
                        q.append((nx, ny))
                        check[nx][ny] = 1
    
        cnt = 0
        for i in range(n):
            for j in range(m):
                if not check[i][j] and grid[i][j] == "1":
                    dfs(i, j)
                    # bfs(i, j)
                    cnt += 1
        return cnt

 

총평

아직까지는 쏘쏘. 감이 남아있다. 그러나 어려운 그래프 문제가 나오면 또 모른다. 좌절할지.