[LeetCode] 200. Number of Islands (파이썬)

200. Number of Islands - 파이썬 풀이

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 코드구현

   문제풀이 아이디어

• 먼저 문제에서 묻는 것에 대해 알아보자. 섬은 물로 모든 면이 둘러 쌓여있고 수평 혹은 수직방향의 인접한 땅들이 모여 이루어진다. 그렇다면 주어진 그리드에서 섬은 몇 개일까?
• 문제에서 설명하듯이 해당 문제에선 격자가 주어진다. 그래서 해당 문제를 격자형 그래프로 생각을 해보자. 그래프는 정점과 정점을 연결하는 간선들을 모아놓은 자료 구조이다. 그리고 해당 문제에선 땅(1)을 하나의 정점으로 볼 수 있고 인접하다는 것을 간선으로 볼 수 있다. 그렇게 되면 인접한 땅(1)이 모여서 하나의 섬이 되는데 이 섬을 그래프=연결요소라고 볼 수 있는 것이다.
• 격자형 그래프에서 하나의 인덱스를 정점이라 생각하고 인접하다는 것을 간선으로 보면 1의 값을 가진 정점이 붙어있는 경우 이동할 수 있다고 생각하면 된다. 간선은 양방향이다. (아래의 그림은 4x4 격자에서의 그래프를 나타낸다.)
  

  

• 그렇다면 연결요소의 개수를 찾기 위해선 무엇을 해야할까? 그리드에서 땅(1)인 인덱스를 시작점으로 해당 그래프의 모든 노드를 탐색하면 하나의 연결요소에 해당하는 노드, 인덱스가 무엇인지 알 수 있고 이것을 그리드 전체에서 겹치지 않는 땅(1)을 시작점으로 수행하면 될 것이다.
• 연결 요소를 구하기 위해서는 그래프 탐색 알고리즘을 사용하면 된다. 대표적으로 BFS, DFS가 존재하는데 이 두 알고리즘 모두 시간, 공간 복잡도 측면에서 O(V+E)로 같다. 하지만 BFS를 사용하는 것이 더 좋을 것같다. 그 이유는 단필자는 BFS가 더 편하기 때문이다.
• BFS의 시간 복잡도는 O(N_M)으로 표현이 된다. 여기선 최대 N = 300, M = 300 으로 주어졌기에 최악의 경우를 생각하면 300_300 = 90,000 의 시간이 소요된다. 이 경우, 원하는 시간 안에 풀이가 가능하다.
• 결론적으로 BFS를 이용하여 주어진 그리드에 대해서 한번도 들리지 않은 땅을 찾고 그 땅을 시작점으로 그래프 탐색을 통해 해당 그래프의 모든 노드를 찾는다. 이를 그리드가 끝날 때까지 반복을 하면 원하는 섬(연결요소)의 개수를 반환할 수 있다.

구현코드

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(n, m, grid, visited, i, j, num):
            dx = (0, 1, 0, -1)
            dy = (1, 0, -1, 0)
            q = deque()
            q.append((i, j))
            visited[i][j] = num
            while q: # 그래프의 모든 연결된 노드를 찾는 부분
                row, col = q.popleft()
                for i in range(4):
                    nr, nc = row + dx[i], col + dy[i]
                    if not (0<=nr<n and 0<=nc<m):
                        continue
                    if grid[nr][nc] == "0" or visited[nr][nc] != 0:
                        continue
                    q.append((nr, nc))
                    visited[nr][nc] = num
        n = len(grid)
        m = len(grid[0])
        visited = [[0]*m for _ in range(n)] # 방문여부를 알기위한 2차원 배열 생성
        num = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1" and visited[i][j] == 0: # 방문 여부와 땅임을 확인하는 부분
                    num += 1 # 섬의 개수를 표현
                    bfs(n, m, grid, visited, i, j, num)
        return num