[leetcode] 200. 섬의 개수 (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 lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.

(연결되어 있는 1의 덩어리 개수를 구하라.)

 

 

입출력 예시

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

 

생각 과정

이 문제를 가지고 DSF(깊이 우선 탐색)과 BFS(넓이 우선 탐색)의 구현을 연습해보자.

당연하게도 내가 푼 코드는 아니고, 책과 강의를 보고 풀었다.

 

풀이

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

 

DSF와 BSF를 이용하기 전에 가장 먼저 이런 유형의 문제를 풀 때, 함께 와야하는 생각은 현재 정점을 기준으로 동서남북을 탐색하는 것이다. 일렬로 이어진 형태로 생각하는 것보단 문제에 주어진 것처럼 행과 열로 생각해야 동서남북으로 어떻게 이동하는 지 알 수 있다.

 

여기서 행은 가로줄 즉, grid의 n번째 리스트 한줄(x)을 의미하며 열은 세로줄, grid의 인덱스값이 늘어나는 방향(y)을 의미한다.

x값이 늘어나면 오른쪽으로 이동하고, y값이 늘어나면 아래로 내려간다.

 

헷갈릴 수 있는데, 행과 열을 인덱스로 표현하면 grid[y][x]이다. 만약 헷갈린다면 x와 y의 의미를 반대로 뒤집자.

 

 

현재 그리드의 가장 첫번째 값(grid[2][3])을 기준으로 동서남북을 이동 해보자. (동서남북이 전부 있는 중간쯔음에 있기 때문에 예시로 삼는다) 우리가 보는 기준으로 위쪽을 북쪽으로 잡겠다.

 

현재 기준점에서 북쪽이나 남쪽으로 이동하려면 y값을 감소시키면 된다. grid[1][3] 혹은 grid[3][3]이 된다.

현재 기준점에서 서쪽이나 동쪽으로 이동하려면 x값을 감소시키면 된다. grid[2][2] 혹은 grid[2][4]가 된다.

 

이 동서남북으로 이동시켜주는 녀석을 이렇게 변수로 담아주고 시작하자

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

 

이제 전체코드를 보면서 흐름과 어떤 식으로 DFS와 BSF가 적용되는지 확인해보자.

 

 

DFS - 재귀 구조

def island_dfs_recursive(grid):
    # 그리드에서 기준점을 상하좌우로 이동시키기 위한 변수
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # 그리드의 전체 범위를 지정하는 함수
    rows, cols = len(grid), len(grid[0])

    # 섬의 개수를 세기 위한 변수
    cnt = 0

    # 재귀 함수
    def dfs_recursive(y, x):
        # 기준점이 grid를 벗어나거나, 섬이 아니면 skip
        if y < 0 or y >= rows or x < 0 or x >= cols or grid[y][x] != '1':
            return

        # 동서남북 노드 확인
        # 기준 노드 방문처리
        grid[y][x] = '0'
        for i in range(4):
            # 재귀
            dfs_recursive(y + dy[i], x + dx[i])
        return

    # 기준 노드를 하나씩 가져온다.
    for r in range(rows):
        for c in range(cols):
            node = grid[r][c]

            # 기준 노드가 섬이 아니면 skip
            if node != '1':
                continue

            # 섬 개수 카운팅
            cnt += 1
            dfs_recursive(r, c)

    return cnt

 

 

먼저 볼 코드는 이 부분이다

# 기준 노드를 하나씩 가져온다.
for r in range(rows):
    for c in range(cols):
        node = grid[r][c]

        # 기준 노드가 섬이 아니면 skip
        if node != '1':
            continue

        # 섬 개수 카운팅
        cnt += 1
        dfs_recursive(r, c)

 

중첩 for문을 이용해서 기준 노드를 grid[0][0]부터 grid[len(rows)][len(cols)]까지 가져온다.

우리는 섬(1)인 부분만 확인할 것이기 때문에 조건문으로 예외 처리를 해준 후, 섬 개수를 카운팅 해준 다음에 dfs_recursive() 함수로 기준 노드 동서남북에 연결된 섬이 있는 지 확인한다. 그래프의 간선을 따라가는 부분이다. 

 

이제 재귀 호출을 하면서 연결된 섬을 확인해보자

# 재귀 함수
def dfs_recursive(y, x):
    # 기준점이 grid를 벗어나거나, 섬이 아니면 skip
    if y < 0 or y >= rows or x < 0 or x >= cols or grid[y][x] != '1':
        return

    
    # 기준 노드 방문처리
    grid[y][x] = '0'
    
    # 동서남북 노드 확인
    for i in range(4):
        # 재귀
        dfs_recursive(y + dy[i], x + dx[i])
    return

 

코드를 하나하나 생각하면서 보면 헷갈리기 망정이다. 재귀를 몇번 보면서 헷갈리던 부분에서 감이 잡히기 시작했는데, 사실상 재귀는 처음 몇번만 호출되는 걸 확인하면 그 뒤까지는 생각할 필요가 딱히 없는 것 같다. 어차피 같은 반복이기 때문이다.

 

코드를 리딩해보자면 우선 예외처리를 해준다. 기준점에서 동서남북 중 grid를 벗어나는 부분이 있거나 섬(1)이 아니라면 return으로 넘겨준다.

그리고나서 기준 노드를 방문 처리 해주는데 이게 grid[y][x] = '0' 부분이다. 우리는 섬이 아닌 곳(0)을 만나면 예외 처리를 해두었기 때문에 이미 탐색한 곳은 0으로 바꿔줘서 다시 탐색하지 않게 해준다.

 

그 후에 동서남북에 있는 노드를 확인하게 되는데, 이 for문을 돌면서 동서남북으로 이동하면서 계속해서 섬과 연결된 부분이 있는 지 확인한다.

 

 

BSF - 큐

def island_bfs(grid):
    # 그리드에서 기준점을 상하좌우로 이동시키기 위한 변수
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 반복할 횟수
    rows, cols = len(grid), len(grid[0])

    # 섬의 개수
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            # 섬이 아니면 skip
            if grid[row][col] != '1':
                continue

            cnt += 1

            # 시작점 세팅 / q는 기준점
            q = deque([(row, col)])

            while q:
                # 기준점을 꺼내준다.
                x, y = q.popleft()

                # 상하좌우가 섬인지 탐색
                for i in range(4):
                    nx = x + dx[i]  # 상 -1   하 1   좌 0     우 0
                    ny = y + dy[i]  # 상 0    하 0   좌 -1    우 1

                    # 이동시킨 점이 grid의 범위를 벗어나면 skip
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue

                    # 이미 탐색한 섬을 0으로 바꿔줌 -> 같은 곳을 다시 탐색하는 것 방지 (방문 표시)
                    grid[nx][ny] = '0'
                    q.append((nx, ny))

    # 섬 개수 반환
    return cnt

 

BSF 역시 기준점에서 상하좌우를 확인하면서 섬(1)으로 되어있는 부분들을 찾고 이미 방문한 점은 방문표시를 해주는 과정의 반복이다.

 

---

마치며

이 섬의 개수 문제의 코드를 계속 어떻게 돌아가는지 이해하려고 돌려봤는데, 전체적인 구현 방식은 기본 DSF, BSF의 구현방식에서 크게 벗어나지 않아 보는건 어렵지 않았지만 디버그 모드로 돌리면서 머리속에서 그림을 그려보려고 하면 잘 안돼서 시간을 많이 쏟았다.

개념 공부를 어제 길게 잡고 했기 때문에 오늘은 구현 연습을 좀 하려고 했는데 고작 이 문제 하나에 시간을 너무 많이 들여버렸다.

 

백준에서 기본적인 문제를 찾아서 공부해야겠다고 다짐했다!