LeetCode 200번 Number of Islands

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

---

문제 파악

주어진 m×n 2D 바이너리 그리드(grid)는 '1' (육지)와 '0' (물)로 구성된 지도를 나타낸다. 이를 통해 섬의 수를 반환하는 문제이다. 섬은 물로 둘러싸여 있으며, 육지는 수평 또는 수직으로 연결되어 있다. 모든 네 모서리는 물로 둘러싸여 있다고 가정할 수 있다. 주변이 물(0)으로 둘러 쌓여있는, 즉, 섬의 개수를 리턴하라!

접근 방법

Grid는 암시적 그래프로 이루어져 있기 때문에 그래프에서 사용되는 탐색 알고리즘을 사용할 수 있다.

그래프 탐색 알고리즘 중 DFS를 사용하면 섬이라고 정의된 영역을 효과적으로 탐색할 수 있다. 섬은 1로 표시되어 있으며, 이들은 서로 인접한 부분들의 집합으로 구성되어 있다. DFS는 한 영역을 발견하면 그 영역을 가능한 한 깊이까지 탐색한다. 따라서 한 1로 이루어진 영역을 발견하면 해당 영역을 완전히 탐색할 수 있다.

DFS나 BFS를 통해 vertex마다 연결되어있는 구조를 파악하고 섬의 개수를 파악해서 이를 count를 통해 추가해주면 될 것 같다.

max가 300이므로 v는 10^5 정도 있는 거고 BFS나 DFS를 통해 시간복잡도는 10^8보다 작으니까 이를 통해서 하면 되겠다!

코드 구현

• BFS

  # BFS
  
  from collections import deque
  
  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          # 기본 값 세팅
          cnt = 0
          row_len = len(grid)
          col_len = len(grid[0])
          visited = [[False] * col_len for _ in range(row_len)]
  
          # BFS 함수 구현
          def bfs(r, c, grid):
              # 방향
              dr = [0, 1, 0, -1]
              dc = [1, 0, -1, 0]
              visited[r][c] = True
  
              # 큐 생성
              q = deque()
              q.append((r, c))
  
              # 반복문을 통해 가는 방향이 1인지 0인지 확인
              while q:
                  cur_r, cur_c = q.popleft()
                  for i in range(4):
                      next_r = cur_r + dr[i]
                      next_c = cur_c + dc[i]
                      if 0 <= r < len(grid) and 0 <= c < len(grid[0]):
                          if grid[r][c] == "1":
                              if visited[next_r][next_c]:
                                  visited[next_r][next_c] = True
                                  q.append((next_r, next_c))
  
          # Grid 순회
          for i in range(row_len):
              for j in range(col_len):
                  # 만약 Grid 값이 1이고 방문하지 않았다면
                  if grid[i][j] == "1" and not visited[i][j]:
                      # BFS를 통해 연결된 모든 1에 대해 방문 표시
                      bfs(i, j, grid)
                      # 섬의 개수 1 증가
                      cnt += 1
  
          return cnt
  

• DFS

  from typing import List
  
  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          # 기본 값 세팅
          cnt = 0
          row_len = len(grid)
          col_len = len(grid[0])
          dr = [0, 1, 0, -1]
          dc = [1, 0, -1, 0]
          visited = [[False] * col_len for _ in range(row_len)]
  
          # DFS 함수 구현
          def dfs(r, c):
              visited[r][c] = True
              for i in range(4):
                  next_r = r + dr[i]
                  next_c = c + dc[i]
                  if 0 <= next_r < row_len and 0 <= next_c < col_len:
                      if grid[next_r][next_c] == "1":
                          if visited[next_r][next_c]:
                              dfs(next_r, next_c)
  
          # Grid 순회
          for i in range(row_len):
              for j in range(col_len):
                  # Grid의 값이 1이고 아직 방문하지 않았다면
                  if grid[i][j] == "1" and not visited[i][j]:
                      # DFS를 통해 연결된 모든 1에 대해 방문 표시
                      dfs(i, j)
                      # 섬의 개수 1 증가
                      cnt += 1
  
          return cnt