[Leetcode/파이썬] 200. Number of Islands

Number of Islands

---

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:
        def bfs(si: int, sj: int) -> None:
            q = deque()
            q.append((si, sj))
            v[si][sj] = 1

            while q :
                ci, cj = q.popleft()
                for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
                    ni, nj = ci + di, cj + dj
                    if 0<=ni<n and 0<=nj<m and grid[ni][nj] == '1' and v[ni][nj] == 0 :
                        q.append((ni, nj))
                        v[ni][nj] = 1


        n, m = len(grid), len(grid[0])
        v = [[0] * m for _ in range(n)]
        cnt = 0

        for i in range(n) :
            for j in range(m) :
                if grid[i][j] == '1' and v[i][j] == 0 :
                    bfs(i, j)
                    cnt += 1

        return cnt

전형적인 그래프 탐색 문제. 

입력

• n, m : 범위 설정
• v : 2차원 배열. 방문 처리를 위해서 생성
• cnt : 섬 숫자 세기

2차원 for loop를 돌면서 grid[i][j] = 1 이면서 아직 방문하지 않았다면 BFS 탐색을 수행한다.

BFS

• q: deque 메소드를 활용해서 양방향 접근. 초기값으로 2차원 i, j 루프의 인덱스를 넣음.
• v: 초기값 방문 처리
• while : 아직 q에 숫자가 남아있다면, 방문할 수 있는 여력이 있는 것이므로 방문 처리 하면서 while loop를 수행
  • q의 가장 앞 부분 (0번째 인덱스에 존재하는 데이터)를 뽑아 현재 위치 curr_i, curr_j 로 받음 (ci, cj) 
  • 다음 이동 단계로 di, dj 를 각 [상 하 좌 우]로 움직이는 범위 내에서 
  • ni, nj : 다음 이동 방향으로 받음. 
  • 범위내, 네방향, 미방문, 조건(grid='1') 설정 => 이 조건이 모두 부합한다면
  • ni, nj를 q에 삽입하고 방문처리를 한다.
  • q에 더 이상 추가되는 ni, nj 가 없을 때 까지 진행
• BFS를 한번씩 수행할때 마다 cnt += 1 를 수행(섬의 개수를 세는 행위)

기계적으로 BFS 를 많이 풀다보니 이런 문제는 대충 봐도 머리 속에 풀이과정이 떠오르게 된다. 좋아해야되나 말아야되나... 싶다.