[파이썬 알고리즘] 12장 - 섬의 개수 (leetcode 200)

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

Number of Islands - LeetCode

<문제>

Given an m x n 2d grid 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.

 

<예시>

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

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

---

1. BFS이용 (breadth first search)

class Solution:
    # 클래스 멤버변수 선언
    grid: List[List[str]]  
    n_row: int
    n_col: int

    def BFS(self, start_i, start_j):
        queue = deque()
        queue.append((start_i, start_j))
        while queue:
            i, j = queue.popleft()
            self.grid[i][j] = '0'
            # 현재 위치에서 상하좌우 탐색해서 갈 수 있는 위치를 queue에 insert
            if i-1 >= 0 and self.grid[i-1][j] == '1' and (i-1, j) not in queue:
                queue.append((i-1, j))  # up
            if i+1 < self.n_row and self.grid[i+1][j] == '1' and (i+1, j) not in queue:
                queue.append((i+1, j))  # down
            if j-1 >= 0 and self.grid[i][j-1] == '1' and (i, j-1) not in queue:
                queue.append((i, j-1))  # left
            if j+1 < self.n_col and self.grid[i][j+1] == '1' and (i, j+1) not in queue:
                queue.append((i, j+1))  # right

    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.n_row, self.n_col = len(grid), len(grid[0])
        n_island = 0
        for i in range(self.n_row):
            for j in range(self.n_col):
                if self.grid[i][j] == '1':
                    n_island += 1
                    self.BFS(i, j)
        return n_island

처음 grid의 모습이다.

 

for i in range(self.n_row):
    for j in range(self.n_col):
        if self.grid[i][j] == '1':
            n_island += 1
            self.BFS(i, j)

i=0, j=0일 때 grid[0][0] == "1" 이므로 BFS 함수가 호출된다.

 

 

(0, 0)에서 상하좌우 방향에 존재하는 위치 중 "1"인 위치만 queue에 넣는다.

그 다음 grid[0][0] = "0"으로 바꾼다.

이후 queue에서 pop한다.

 

(0, 1)에서 상하좌우 방향에 존재하는 위치 중 "1"인 위치한 queue에 넣는다. (그 위치가 (1, 1))

그 다음 grid[0][1]을 "0"으로 바꾼다.

이후 queue가 비어있지 않으므로 queue에서 pop하고, (1, 0)이 리턴된다.

 

(1, 0)에서 상하좌우 방향에 존재하는 위치 중 "1"인 위치를 queue에 넣는다.

여기서는 (1, 1)이지만 이미 queue에 들어가있기 때문에 다시 push하지는 않는다.

그 다음 grid[1][0]을 "0"으로 바꾼다.

이후 queue가 비어있지 않으므로 queue에서 pop하고, (1, 1)이 리턴된다.

 

(1, 1)의 상하좌우 방향에 "1"인 위치가 없으므로 queue에 push하지 않는다.

그리고 현재 위치를 "0"으로 바꾼다.

queue가 비어있으므로 BFS 함수를 return된다.

 

 

for i in range(self.n_row):
    for j in range(self.n_col):
        if self.grid[i][j] == '1':
            n_island += 1
            self.BFS(i, j)

이후 다시 for문을 돌다가 (2, 2) 위치에서 BFS 함수가 다시 호출된다.

 

이런식의 과정을 반복하면 최종적으로 섬의 개수를 구할 수 있게 된다 🙂

 

 

2. DFS이용 (depth first search)

class Solution2:
    grid: List[List[str]]  # class member 변수
    n_row: int
    n_col: int

    def dfs(self, i, j):
        if i < 0 or i >= self.n_row or j < 0 or j >= self.n_col or self.grid[i][j] == '0':
            return

        self.grid[i][j] = '0'
        self.dfs(i-1, j)  # down
        self.dfs(i+1, j)  # up
        self.dfs(i, j-1)  # left
        self.dfs(i, j+1)  # right

    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.n_row, self.n_col = len(grid), len(grid[0])
        n_island = 0
        for i in range(self.n_row):
            for j in range(self.n_col):
                if grid[i][j] == '1':
                    self.dfs(i, j)
                    n_island += 1
        return n_island

 

DFS를 이용한 위의 풀이도 유사하다.

다만 재귀를 이용해서 DFS를 구현했다는 것만 다르다.