[LeetCode] 200. Number of Islands

문제 링크: https://leetcode.com/problems/number-of-islands/description/

Number of Islands - LeetCode

코드

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        row = len(grid)
        col = len(grid[0])
        visited = [[False]*col for _ in range(row)]
        q=deque()
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1" and not visited[i][j]:
                    visited[i][j] = True
                    cnt += 1
                    q.append((i,j))
                    while q:
                        x,y = q.popleft()
                        for t in range(4):
                            nx = x+dx[t]
                            ny = y + dy[t]
                            if 0<=nx<row and 0<= ny < col and grid[nx][ny] == "1" and not visited[nx][ny]:
                                visited[nx][ny] = True
                                q.append((nx,ny))

        return cnt

 

풀이

• 기본적인 BFS문제이다.
• grid[i][j]를 탐색하다 아직 방문하지 않았으면서, 1일때 q에 들어가게 된다.
• q에 들어갈때가 섬의 시작지점이므로 cnt를 1 증가시킨다.