200. Number of Islands

문제

Given a 2d grid map of '1's (land) and '0's (water), count 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

풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        board = [list(map(int, row)) for row in grid]
        def dfs(i, j):
            if i < 0 or i >= len(board): return
            if j < 0 or j >= len(board[0]): return
            if board[i][j] == 0: return
            
            board[i][j] = 0
            
            dfs(i - 1, j)
            dfs(i, j - 1)
            dfs(i + 1, j)
            dfs(i, j + 1)
            
        ans = 0
        for i, _ in enumerate(board):
            for j, _ in enumerate(board[0]):
                if board[i][j] == 1:
                    dfs(i, j)
                    ans += 1
                
        return ans

input으로는 좌표와 같은 2차원 배열이 주어진다. 배열은 1과 0으로 이루어져 있으며 1은 육지, 0은 바다로 가정한다. 문제는 4면이 바다로 이루어져 있는 육지의 개수를 구하는 것이다. 모든 좌표를 탐색하면서 육지인지 바다인지 확인하는 작업이므로 dfs와 bfs로 모두 풀 수 있는 문제이다.

나의 경우에는, 좌표를 돌면서 육지를 먼저 찾고 같은 육지로 인식이 되는 지점들을 바다(0)으로 만들어주는 작업을 반복하도록 코드를 작성했다. 육지(1)를 찾게 되면 4면을 모두 확인해서 육지(1)이면 0으로 바꿔주는 작업을 반복하여 좌표 안에는 오로지 육지의 개수만큼 1이 존재하도록 하였다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        board = [list(map(int, row)) for row in grid]
        visited = [[False] * len(grid[0]) for _ in grid]
        dx = [-1,0,1,0]
        dy = [0,-1,0,1]
        ans = 0
        def bfs(i, j):
            q = []
            q.append([i,j])
            while q:
                x, y = q.pop(0)
                for a,b in zip(dx, dy):
                    nx = x + a
                    ny = y + b
                    if 0 <= nx < len(board) and 0 <= ny < len(board[0]):
                        if not visited[nx][ny]:
                            if board[nx][ny] == 1:
                                visited[nx][ny] = True
                                q.append([nx,ny])

        for i, _ in enumerate(board):
            for j, _ in enumerate(board[0]):
                if board[i][j] == 1:
                    if not visited[i][j]:
                        bfs(i, j)
                        ans += 1

        return ans

앞서 언급했듯이, 이번 문제는 bfs를 사용해서 풀 수도 있었다. 이동할 수 있는 거리를 미리 설정한 뒤에, 이어진 육지를 더 이상 탐색할 수 없을 때까지 탐색한 뒤에 다음 육지로 넘어가는 과정을 거친다.