[Leetcode] Number of Islands (BFS 풀이)

출처

https://leetcode.com/problems/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.

 

입출력 예시

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

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

제한사항

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

 

풀이

저번에 푼 넘버오브아일랜드를 bfs 방법으로 푼 방법

우선 아이디어는 다음과 같다

 

1. grid 인자와 같은 크기의 visited_grid 2D array를 선언한다. 

2. 큐를 선언하고 (파이썬 deque사용) 연결된 모든 1을 큐에 넣고, 이 때 1의 값을 인덱스[i,j] 로 표기한다

3. grid 순회를 돌며 visited_grid에 들어간 인덱스가 있으면 스킵하고

4. 아니면 카운터변수 증가시킨다

 

쓰고나니 간단한 아이디어인데 왜 풀땐 어려운지? 역시 훈련만이 답이다

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #grid와 크기가 같은 2d array initialize
        visited_grid = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        cnt = 0
    
        # array 순회 row* column
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # row, column에 있는애가 1이고 visited에 마크가 안되어 있으면 
                if grid[i][j] == '1' and not visited_grid[i][j]:
                    self.bfs(grid,visited_grid,i,j)
                    cnt += 1
        
        return cnt
    
    def bfs(self, grid, visited_grid,i,j):
        dx = [0,1,0,-1]
        dy = [-1,0,1,0] 
        q= collections.deque()
        q.append([i,j])
        visited_grid[i][j] = 1
        
        # q에 원소가 있을 때까지 while문을 돌림
        while q:
            visited_i, visited_j = q.popleft() #visited에 들어간 애들을 꺼내서 그 다음 방향을 지정
            for k in range(4):
                next_x = visited_i + dx[k]
                next_y = visited_j + dy[k]    

                if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >=len(grid[0]) or grid[next_x][next_y] == '0' or visited_grid[next_x][next_y]:
                    continue
                q.append([next_x, next_y])
                visited_grid[next_x][next_y] = 1

 

여담

뭔가 재밌게 술술 쓰고 싶은데 그렇게 되지 않는구만.  . .. .?!

보시고 이해안가는 부분 있으면 댓글 주세요