[Leetcode 아주 상세한 문제풀이] 200. Number of Islands

Leetcode/Graph

[Leetcode 아주 상세한 문제풀이] 200. Number of Islands - 코드 line 별 설명

PhD엔지니어 2023. 12. 27. 05:05

Leetcode 문제

이번에 풀어볼 문제는 리트코드 200번 문제 Number of Islands 이다.

우선 문제를 살펴보자.

Can you solve this real interview question? Number of Islands - 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 l

leetcode.com

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'.

문제 설명

문제에 대해 간략히 살펴보자. m x n 사이즈인 2D 배열이 주어진다. 이 2D 배열은 0과 1로만 이루어진 binary 배열이다. 이때 0은 물 (혹은 바다)로 1을 땅 (혹은 육지)으로 인식할 것이다. 이때 주어진 2D 배열에서 섬의 개수를 찾아내라는 문제다. 글로 설명하는 것 보다는 배열을 직접 보는 것이 더 좋을 것 같다.

예를 들어 문제 예시 1번의 경우 숫자 1을 빨간색으로 표시해보면 연속으로 이어진 땅 (=1)은 1갭밖에 존재하지 않기 때문에 결국 섬의 개수는 1개라고 할 수 있다. 문제 예시 2번의 경우 똑같이 1을 빨간색으로 표시해보면 연속으로 이어진 땅 (=1)은 3개가 존재하게 되므로 섬의 개수는 3개라고 할 수 있다. 여기서 중요한 것은 배열 가운데쯤 존재하는 1은 단 1개만 존재하지만 어쨋든 바다 (=0)로 둘러쌓인 육지 (=1)이기 때문에 섬으로 인식해야 한다는 점이다.

문제 접근법

우리는 이 문제를 해결하기 위하여 Depth First Search (DFS) 방식을 이용할 것이다.

주어진 2D 배열에서 숫자를 하나씩 탐색할 것인데, 우리는 해당 숫자가 1인경우 상하좌우를 살펴볼 것이다.

해당 숫자가 0인 경우 바다이기 때문에 관심 밖이기 때문이다.

이해를 돕기 위해 예를 들어 설명해 보겠다.

예시1

문제 예시보다 좀 더 작은 3 x 3 배열이 아래와 같이 주어졌다고 생각해보자.

  ["1","0","1"],
  ["0","1","0"],
  ["1","0","1"]

이 배열에서 1이 모두 떨어져 있기 때문에 우리는 한 눈에 정답이 5개라는 것을 알 수 있다.

하지만 알고리즘화 시켜 풀기 위해서는 다음과 같이 접급해야 한다.

우선 (0,0)을 탐색해보자. 이 경우 해당 숫자가 1이기 때문에 다른 1과 이어져 있는지 상하좌우를 탐색해 본다.

'상'과 '좌'는 숫자가 존재하지 않기 때문에 더 이상 탐색할 필요가 없고,

'하'와 '우'는 숫자가 존재하는데 그 숫자가 0이기 때문에 더 이상 탐색할 필요가 없이

우리가 탐색하고 있는 (0,0)에 있는 숫자 1은 '섬'이라고 확인할 수 있다.

그리고 중요한 점은 탐색한 숫자들은 반드시 0으로 변경해 줘야 한다는 것이다.

그렇지 않는다면 이전 탐색에서 확인된 숫자 1들 끼리 연결된 섬인데도 불구하고 double counting이 될 수도 있기 때문이다.

예시2

이해를 돕기 위해 한 가지 예를 더 들어보자.

위 예시와 동일하지만 (0,1)자리에 1이 있어 더 큰 섬을 이루고 있는 3 x 3 배열이 아래와 같이 주어졌다고 생각해보자.

  ["1","1","1"],
  ["0","1","0"],
  ["1","0","1"]

이 배열에서 우리는 (0,0)자리에 1이 있음을 확인하고 상하좌우를 탐색한다.

이때 '우'에 1이 위치하기 때문에 그 자리 (0,1)을 기준으로 다시 상하좌우를 탐색한다.

그렇게 되면 '하' (0,2) 와 '우' (1,1) 자리에 1이 존재함을 알 수 있다.

그리고 앞서 설명한대로 탐색한 후 해당 1을 0으로 변경해줘 double counting을 피한다.

이 과정을 반복하다보면 처음 DFS탐색 후 다음과 같이 배열이 변하게 된다.

  ["0","0","0"],
  ["0","0","0"],
  ["1","0","1"]

즉, 1로 이루어진 가장 큰 섬 탐색이 끝남에 따라 우리는 섬의 개수 1개를 카운팅 해주고,

동시에 탐색된 숫자를 0으로 변경해 줌으로써 두번 카운팅 되는 문제를 방지한다.

결국 이 경우도 DFS 탐색을 반복하다보면 최종적으로 섬의 개수가 3개임을 알 수 있고,

주어진 배열의 모든 숫자는 0으로 변하게 되어 탐색이 종료된다.

이제 코드로 한 번 살펴보자.

문제 풀이

2D 배열을 입력받을 함수를 정의해 준다 (line 1)

반약 입력받은 배열이 비어있다면 0을 리턴해주고 종료한다 (line 2-3)

앞서 설명한 바와 같이 우리는 주어진 배열의 모든 행과 열을 탐색할건데 (line 19-20)

만약 탐색하는 숫자가 '1'이라면 DFS 탐색을 시작한다 (line 21-22)

탐색을 위해 dfs 함수를 정의해준다 (line 9)

이때 탐색하고 있는 행과 열이 0보다 작거나 (즉, 주어진 grid 밖이거나)

혹은 주어진 2D 배열보다 크거나 혹은 그 값이 0이라면 탐색을 종료한다. (line 10-11)

이 경우가 아니라면 앞서 설명한대로 탐색한 지점은 재탐색을 하지 않도록 0으로 변환해준다 (line 12)

그리고 dfs함수를 재귀하여 상하좌우를 탐색한다 (line 14-17)

이 과정을 반복하게 되면 탐색한 숫자들은 모두 0으로 변하게 되고,

모든 탐색을 마쳤을 때 그 지점까지가 '하나의 섬'이기 때문에

섬의 개수를 카운트 하는 num_islands에 1을 더해주며 해당 위치 탐색을 종료한다. (line 23)

Double for loop를 이용하여 주어진 2D 배열 모두를 탐색하고,

최종적으로 우리가 찾고자 하는 섬의 개수를 리턴해준다 (line 25)

문제 풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def numIslands(grid):
    if not grid:
        return 0
 
    rows, cols = len(grid), len(grid[0])
    num_islands = 0
 
    # DFS function to traverse the island
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # Mark the cell as visited
        # Visit all four directions
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                num_islands += 1
 
    return num_islands
 
# Test cases
grid1 = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(numIslands(grid1))  # Output: 1
 
grid2 = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(numIslands(grid2))  # Output: 3
 
Colored by Color Scripter

cs

[Leetcode 아주 상세한 문제풀이] 207. Course Schedule - 코드 line 별 설명 (1)	2023.12.27
[Leetcode 아주 상세한 문제풀이] 128. Longest Consecutive Sequence – 코드 line 별 설명 (0)	2023.12.27

PhD 엔지니어의 테크월드