LeetCode - 200. Number of Islands [Python]

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

Number of Islands - LeetCode

---

풀이 과정

지도에서 땅으로 연결된 섬의 개수를 찾는 문제이다.

 

그래프에서 연결 요소를 찾으라는 문제인데, 지도의 모든 칸에 대해 dfs 혹은 bfs로 방문하면 연결요소의 개수를 찾을 수 있다.

 

보통 visited 이차원 배열을 선언해서 이전에 방문했는지를 판별하는데, 이 문제는 이차원 배열을 선언하지 않고 이미 방문한 땅을 물로 바꿔주면 방문했던 곳을 다시 방문하는 것을 막을 수 있다. 이러면 메모리 효율성이 증가한다.

 

지도를 보면서 땅인 부분을 bfs로 방문하고, 정답 변수를 1 증가시켜주고, 방문한 땅 및 그와 연결된 땅을 전부다 물로 바꿔주는 방법으로 문제를 해결할 수 있다.

 

bfs를 중첩 함수로 만들고 지도에서 땅인 부분을 방문하게끔 하였다.

---

소스 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        answer = 0
        def bfs(start_y, start_x):
            grid[start_y][start_x] = 0
            Q = collections.deque([[start_y, start_x]])
            while Q:
                v = Q.popleft()
                for i in range(4):
                    ny = v[0] + dy[i]
                    nx = v[1] + dx[i]
                    if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] == "1":
                        Q.append([ny, nx])
                        grid[ny][nx] = 0
                        
                        
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    bfs(i, j)
                    answer += 1
        return answer