[Leetcode] DFS/BFS - Number of Islands

문제 

 

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

Number of Islands - LeetCode

 

 

gird는 "1"(land)과 "0"(water)으로 이루어진 지도를 표현하는 m x n 이차원배열이다. 이 지도에 표시된 섬들의 총 갯수를 반환하시오. 섬이란 수평과 수직으로 땅이 연결되어 있고 주변은 물로 둘러쌓여있는 것을 말한다. 또한, grid의 네개의 가장자리는 모두 물로 둘러쌓여있다고 가정하고 문제를 해결하라.

 

 

제약조건

 

1. m == grid.length

2. n == grid[i].length

3. 1 <= m,n <= 300 → 300x300은 900으로 약 10^5이므로 O(n^2) 미만 시간복잡도로 풀어야한다는 단서이다.

4. grid[i][i] is '0' or '1'

 

 

구현

 

→ BFS

from collections import deque

def numIslands(grid):
    numsOfIslands = 0
    rowLength = len(grid) #4
    colLength = len(grid[0]) #5
    visited = [[False] * colLength for _ in range(rowLength)]

    def bfs(r,c):
        gx = [-1, 1, 0, 0]
        gy = [0, 0, -1, 1]
        q = deque()
        q.append((r,c))
        visited[r][c] = True
        while q:
            cx, cy = q.popleft()
            for i in range(4):
                next_x = cx + gx[i]
                next_y = cy + gy[i]
                if 0 <= next_x and next_x < rowLength and 0 <= next_y and next_y < colLength:
                    if grid[next_x][next_y] == "1" and visited[next_x][next_y] == False:
                        visited[next_x][next_y] = True
                        q.append((next_x, next_y))
        
        
    for i in range(rowLength):
        for j in range(colLength):
            if grid[i][j] == "1" and visited[i][j] == False:
                    bfs(i, j)
                    numsOfIslands += 1

    return numsOfIslands

 

 

→ DFS

def numOfIslands(grid):
    num = 0
    lowLen = len(grid)
    colLen = len(grid[0])
    visited = [[False] * colLen for _ in range(lowLen)]

    def dfs(r, c):
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        visited[r][c] = True
        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]
            if 0 <= nx and nx < lowLen and 0 <= ny and ny < colLen:
                if grid[nx][ny] == "1" and visited[nx][ny] == False:
                    dfs(nx, ny)
    
    for i in range(lowLen):
        for j in range(colLen):
            if grid[i][j] == "1" and visited[i][j] == False:
                dfs(i,j)
                num += 1
    return num