[LeetCode]Number of Islands

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

2차원 그리드에서 1로 연결이 된 섬의 갯수를 구하는 문제입니다.

 

처음 시도한 답안 - DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i: int, j: int) -> None:
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == "0":
                # If the current cell is out of bounds or is water (0) or has already been visited, return.
                return

            grid[i][j] = "0" # Mark the current cell as visited.
            dfs(i+1, j) # Visit the neighbor to the right.
            dfs(i-1, j) # Visit the neighbor to the left.
            dfs(i, j+1) # Visit the neighbor below.
            dfs(i, j-1) # Visit the neighbor above.
        
        m, n = len(grid), len(grid[0]) # Get the dimensions of the given matrix.
        count = 0 # Initialize a count variable to 0.
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1": # If we encounter an unvisited 1, increment the count and perform a DFS on its neighbors, marking all the visited 1's as visited.
                    count += 1
                    dfs(i, j)

        return count # Return the count of the number of islands.

접근 방법

1. DFS를 통해 1로 연결이 된 섬을 탐색합니다.
2. 이중 루프를 활용해 Grid를 순회합니다.
3. 만약 그리드가 1 이라면 (섬이라면)
   1. dfs를 통해 0으로 방문 처리를 합니다.
   2. 방문 처리했으니 카운트를 1 증가합니다.
4. DFS 내부에서
   1. 그리드를 벗어나지 않고 & 0이 아닌 곳을 방문합니다.
   2. 방문한 지점은 0으로 방문 처리를 합니다.
   3. 상하좌우로 방문합니다.

DFS를 통해 섬을 방문처리하면서 카운트를 구하는 방법입니다. BFS로도 풀이가 가능하여 시도해보았습니다.

 

두번째로 시도한 답안 - BFS

from collections import deque


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        count = 0

        def bfs(i, j):
            queue = deque([(i,j)])

            dx = [0,-1,0,1]
            dy = [1,0,-1,0]

            while queue:
                i, j = queue.popleft()

                for idx in range(4):
                    x = i + dx[idx]
                    y = j + dy[idx]

                    if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] == "0":
                        continue

                    queue.append((x,y))
                    grid[x][y] = "0"


        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1
                    bfs(i, j)

        return count

접근 방법

1. BFS로 그리드를 순회합니다.
2. 이중 루프를 통해 Grid를 순회합니다.
   1. 만약 1이라면 (섬이라면)
   2. bfs로 방문 처리를 하고 카운트를 증가합니다.
3. BFS 내부에서 순회하려는 그리드를 큐에 삽입합니다.
   1. 큐에 들어있는 요소를 pop합니다.
   2. 상하좌우로 이동이 가능한지 확인후 가능하다면 큐에 넣습니다.
   3. 큐에 넣은 지점을 방문처리합니다.

연결된 섬을 순회하는 방법으로 BFS를 사용했습니다.