38. Number of Islands(bfs, dfs)

문제

1(땅)과 0(바다)으로 이루어진 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

 

해결 방식 1) BFS

1) i, j로 그리드 탐색하다가 1을 만나면

2) 섬 카운트 1 증가.

3) bfs 함수 호출 

   가) 현재 i, j를 튜플로 만들어 queue에 넣음

   나) queue에 있는 요소를 pop

   다) 꺼낸 요소(예: grid[i][j])의 상하좌우에 1이 있는지 확인

   다) 1이 있으면 이동한 곳의 인덱스를 튜플로 만들어 queue에 넣음

   라) 이동한 곳의 1은 0으로 변경

   마) 큐가 빌 때까지 나) ~ 라) 과정 반복

   => 섬이 끝나면 호출 종료

4) 탐색 재개. 1) ~ 3) 과정 반복 

from collections import deque 

class Solution:
    def bfs(self, grid, i, j):
        # 큐에 현재 i, j 튜플 추가
        queue = deque([(i, j)])
        row_length, column_length = len(grid), len(grid[0])
        while queue:
            row, col = queue.popleft()
            # 우측, 아랫쪽, 좌측, 윗쪽 방향 
            directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
            
            # 네 방향에 1이 있는지 모두 체크함
            for direction in directions:
                new_i, new_j = row + direction[0], col + direction[1]
                # 한 칸 이동했는데 거기가 그리드 안쪽이고 1이면
                if (0 <= new_i < row_length) and (0 <= new_j < column_length) and grid[new_i][new_j] == '1':
                    # 이동한 곳을 0으로 바꿈
                    grid[new_i][new_j] = 0
                    # 큐에 이동한 지점 추가
                    queue.append((new_i, new_j))
                    
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                # 현재 요소가 1이면 서치 시작
                if grid[i][j] == '1':
                    count += 1
                    self.bfs(grid, i, j)
        return count

 

해결 방식 2) DFS

1) i, j로 그리드 탐색하다가 1을 만나면

2) 섬 카운트 1 증가.

3) dfs 함수 호출 

   가) 현재 i, j를 튜플로 만들어 stack에 넣음

   나) stack에 있는 요소를 pop

   다) 꺼낸 요소(예: grid[i][j])의 상하좌우에 1이 있는지 확인

   다) 1이 있으면 이동한 곳의 인덱스를 튜플로 만들어 stack에 넣음

   라) 이동한 곳의 1은 0으로 변경

   마) 스택이 빌 때까지 나) ~ 라) 과정 반복

   => 섬이 끝나면 호출 종료

4) 탐색 재개. 1) ~ 3) 과정 반복 

class Solution:
    def dfs(self, grid, i, j):
        stack = [(i, j)]
        row_length, column_length = len(grid), len(grid[0])
        
        while stack:
            row, col = stack.pop()
            directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
            for direction in directions:
                new_i, new_j = row + direction[0], col + direction[1]
                
                if 0 <= new_i < row_length and 0 <= new_j < column_length and grid[new_i][new_j] == '1':
                    grid[new_i][new_j] = 0
                    stack.append((new_i, new_j))
    
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)
        return count