[LeetCode] 200. Number of Islands 파이썬 Medium

200. Number of Islands

문제 해석:

2차원 바이너리 그리드에서 1은 땅이고 0은 물이다.
그렇다면 이어져있는 땅의 갯수를 세어야한다.

문제 해설:

1. BFS를 진행해서 이어져있는 섬들을 찾아야한다.
2. BFS를 실행하면 모든 이어진 섬을 찾을 수 있는데, 떨어져있는 섬이 존재할 수도 있다.
3. 2중 for문을 사용해서 모든 그리드의 섬을 하나씩 확인해봐야한다.
4. 그리드 리스트에 들어가있는 숫자가 문자라서 그부분을 조심하자.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Example 2:

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

 

해설 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ans = 0
        # 큐는 리스트로 사용
        q = []
        m = len(grid)
        n = len(grid[0])
        # BFS 방문 배열 생성
        visited = [[0] * n for _ in range(m)]
        dir = [
            [1,0],
            [0,1],
            [-1,0],
            [0,-1]
        ]
        # 모든 칸을 확인해서 시작점으로 잡아야함
        for y in range(m):
            for x in range(n):
            	# 섬이 아니거나, 방문했다면 스킵
                if grid[y][x] == "0":
                    continue
                if visited[y][x] == 1: 
                    continue
                q.append([y, x])
                visited[y][x] = 1
                # BFS 시작이라면 그곳은 방문하지 않은 섬, 카운트 시작
                ans += 1
                # BFS 시작
                while(q):
                    curNode = q.pop()
                    for i in range(4):
                        nxtY = curNode[0] + dir[i][0]
                        nxtX = curNode[1] + dir[i][1]
                        if nxtY >= m or nxtX >=n or nxtY < 0 or nxtX < 0:
                            continue
                        if visited[nxtY][nxtX] == 1:
                            continue
                        if grid[nxtY][nxtX] == "0":
                            continue
                        visited[nxtY][nxtX] = 1
                        q.append([nxtY,nxtX])
        return ans