[LeetCode] 200. Number of Islands

말하는 감자·2024년 11월 15일
BFSDFSGraphleetcodepython그래프코딩테스트코딩테스트 준비파이썬
1

LeetCode

목록 보기
9/32
post-thumbnail

안녕하세요. 오늘 문제는 그래프 순회의 가장 대표적인 문제를 풀어보도록 하겠습니다.

1. 오늘의 학습 키워드

  • Graph
  • DFS
  • BFS

2. 문제: 200. Number of Islands

Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 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

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

3. 문제 풀이

0과 1로 이루어진 이진 grid가 주어집니다. 1은 땅, 0은 물을 의미합니다. 이 grid에 표시된 섬들의 개수를 반환하는 문제입니다. 섬이란 수평과 수직으로 땅이 열결되어 있고 주변은 물로 둘러 쌓여있는 것을 말합니다.

그럼 문제를 좀 더 깊게 살펴보겠습니다.

Step1. 문제 이해하기

  • Input:
    • grid의 길이는 m, grid[i]의 길이는 n이며 m과 n의 길이는 1보다 크거나 같고 300보다 작거나 같습니다.
    • 즉, row개수는 m, col 개수는 n을 의미합니다. 그렇다면 gird에 포함되는 요소의 개수는 1과 9 * 10410^4 인것을 알 수 있습니다.
    • grid의 크기가 10^4이기 때문에 시간복잡도가 O(n2)O(n^2)보다 작아야 할 것으로 예상됩니다.
  • Ouput:
    • 섬의 개수를 반환해야 합니다.

Step2. 문제 분석하기

해당 문제는 0과 1로 이루어진 grid로 그래프를 표현한 문제입니다. 즉, 암시적으로 연결되어있음을 직접적으로 표현하지 않고 상태에 따라 정점을 0과 1로 표기한 그래프입니다.

그래프 문제는 크게 그래프 순회 알고리즘인 DFS, BFS를 활용하는 문제나 그래프를 구현하는 문제로 나눌 수 있습니다.

해당문제는 암시적 그래프(격자)로 나타내었기 때문에 순회 알고리즘을 사용하여서 땅을 찾아서, 이 땅이 섬인지 아닌지를 판단헤야 하기 때문에 순회 문제입니다.

즉, 정점을 모두 순회 하면서 섬을 찾는 그래프 순회 문제입니다!! 그럼 시간복잡도가 O(n)O(n)으로 구성이 될 것입니다.

첫 번째 예시를 통해 좀 더 순회를 어떻게 적용될 지 살펴보겠습니다.

위 그림 처럼 왼쪽 맨 위에서 부터 BFS를 시작하면 이처럼 순회를 시작합니다.

그 다음 정점에서도 마찬가지로 BFS를 시작합니다.

하지만, 이미 1번에서 BFS를 시작했기 때문에 겹치는 것을 확인할 수 있습니다. 이렇다는 것은 나중에 조건문으로 제외해줄 수 있겠죠?

DFS알고리즘도 BFS 알고리즘과 마찬가지로 적용됩니다. 다만 순회 순서만 다를 뿐인것이죠!

자, 이제 문제를 어느정도 분석이 완료되었습니다. 이제 코드를 설계하러 가볼까요?

Step3. 코드 설계

가로, 세로 반복문을 돌면서 gird[i][j] == 1이고 아직 방문하지 않은 상태면 BFS/DFS 알고리즘을 진행해서 그래프 순회를 진행합니다. 그렇게 순회를 진행하면 해당 위치는 섬을 의미하기 때문에 카운트를 합니다.

이렇게 코드를 설계할 수 있을것 같습니다.

그러면 이제, 코드 구현을 진행해보겠습니다.

Step4. 코드 구현

BFS

from collections import deque
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        cnt = 0
        m = len(grid)
        n = len(grid[0])
        visited = [[False] * n for _ in range(m)]
    
        def bfs(x,y):
            dx = [-1,1,0,0]
            dy = [0,0,-1,1]
            visited[x][y] = True
            q = deque()
            q.append((x,y))
            while q:
                cur_x,cur_y = q.popleft()
                
                for r in range(4):
                    next_x = cur_x + dx[r]
                    next_y = cur_y + dy[r]
                    if 0 <= next_x and next_x < m and next_y >= 0 and next_y < n:
                        if grid[next_x][next_y] == '1' and not visited[next_x][next_y]:
                            visited[next_x][next_y] = True
                            q.append((next_x,next_y))
                    

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and not visited[i][j]:
                    bfs(i,j)
                    cnt += 1
        return cnt

코드 설명:

  • 방문 배열 초기화 visited 배열은 주어진 grid와 동일한 크기의 2D 리스트로, 특정 좌표가 방문되었는지 확인합니다.
  • BFS 함수 정의
    • 시작 좌표 (x, y)를 큐에 추가하고, 해당 좌표를 방문 처리합니다.
    • 상하좌우 방향(dx, dy)으로 이동하며, 범위 안에 있고, 아직 방문하지 않았으며, grid 값이 '1'인 경우만 계속 순회합니다.
    • 큐를 통해 연결된 모든 땅을 방문 처리하여 같은 섬에 속한 영역을 탐색합니다.
  • 순회와 섬 개수 카운트
    • grid의 모든 좌표를 탐색하며, 새로운 땅(grid[i][j] == '1'이고 방문되지 않은 경우)을 발견하면 BFS를 호출합니다.
    • BFS 호출 후, 섬 개수를 하나 증가시킵니다.

시간 복잡도: O(m∗n)O(m * n)

결과:

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

DFS

class Solution(object):
# DFS
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        cnt = 0
        m = len(grid)
        n = len(grid[0])
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        visited = [[False] * n for _ in range(m)]
        
        def dfs(x,y):
            visited[x][y] = True
            for i in range(4):
                next_x = x + dx[i]
                next_y = y + dy[i]
                if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n:
                    if grid[next_x][next_y] == "1" and not visited[next_x][next_y]:
                        dfs(next_x, next_y)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and not visited[i][j]:
                    dfs(i,j)
                    cnt += 1
        return cnt

코드 설명:

  • DFS 함수 정의
    • 현재 좌표를 방문 처리하고, 상하좌우 방향으로 재귀적으로 탐색합니다.
    • 탐색 조건은 BFS와 동일합니다. 범위 안에 있고, 방문하지 않았으며, grid 값이 '1'인 경우에만 재귀 호출을 진행합니다.
  • 순회와 섬 개수 카운트
    • 모든 좌표를 순회하며 새로운 땅을 발견하면 DFS를 호출하고, 호출이 끝난 뒤 섬 개수를 하나 증가시킵니다.

시간 복잡도: O(m∗n)O(m * n)

결과:

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

4. 마무리

이번 문제는 그래프 순회의 대표적인 예제로, BFS와 DFS 모두 사용할 수 있음을 보여줍니다. BFS는 큐를 사용해 넓이 우선으로 탐색하고, DFS는 재귀적으로 깊이 우선 탐색을 진행합니다. 두 접근법 모두 섬을 탐색할 때 적합하며, 코드 구현도 비슷한 구조를 가집니다.

이 문제를 통해 다음을 배울 수 있었습니다:

  1. 격자형 그래프의 암묵적 연결 표현.
  2. BFS와 DFS를 활용한 그래프 순회 방법.
  3. 방문 처리와 연결 요소 탐색의 중요성.

다음 단계로는 Union-Find를 활용한 풀이를 학습해보는 것도 추천합니다. Union-Find는 연결 요소를 효율적으로 관리할 수 있는 자료구조로, 이 문제의 최적화된 풀이로 활용될 수 있습니다. 추후에 union-find 알고리즘을 학습 시, 다시 이 문제로 돌아오겠습니다!
전체 코드는 다음 링크에서 확인하실 수 있습니다.
읽어주셔서 감사합니다.

매일 매일 발전하는 개발자가 될거야!!

profile
말하는 감자
할 수 있다
이전 포스트

[LeetCode] 104. Maximum Depth of Binary Tree

다음 포스트

[LeetCode] 1091. Shortest Path in Binary Matrix

0개의 댓글