Leetcode 200

Number of Islands

bfs를 사용한 풀이

언어: python3

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        height = len(grid)
        width = len(grid[0])
        visited = [[False for col in range(width)] for row in range(height)]
        queue = collections.deque([])
        count = 0
        direction = [(0,1),(0,-1),(1,0),(-1,0)]
        for i in range(height):
            for j in range(width):
                if visited[i][j] == False and grid[i][j] == '1':
                    queue.append((i,j))
                    count +=1
                    visited[i][j] = True
                    
                    while queue: # while deque is not empty
                        y,x = queue.popleft()
                        for k in range(4):
                            nexty = y+ direction[k][0]
                            nextx = x+ direction[k][1]
                            condition = (nexty < height) and (nexty>=0) and (nextx<width) and (nextx>=0)    
                        
                            if condition and visited[nexty][nextx] == False and grid[nexty][nextx] == '1':
                                queue.append((nexty,nextx))
                                visited[nexty][nextx] = True
                    
        return count

deque 사용한 이유: popleft O(1)에 수행하기 위해서
그냥 queue에서는 O(N) 시간에 수행

dfs를 사용한 풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        height = len(grid)
        width = len(grid[0])
        visited = [[False for col in range(width)] for row in range(height)]
        direction = [(0,1),(0,-1),(1,0),(-1,0)]
        count = 0
        
        def dfs(y,x):
            if y >= height or y<0 or x >= width or x<0:
                return
            visited[y][x] = True
            for k in range(4):
                nexty = y+direction[k][0]
                nextx = x+direction[k][1]
                if nexty < height and nexty>=0 and nextx < width and nextx>=0:
                    if visited[nexty][nextx] == False and grid[nexty][nextx]=='1':
                        dfs(nexty,nextx)
                
        for i in range(height):
            for j in range(width):
                if visited[i][j] == False and grid[i][j]=='1':
                    count += 1
                    dfs(i,j)
                    
        return count