[리트코드] Number of Islands(python)

리트코드, Number of Islands_섬의 수

 

TL;DR

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

문제 분석

1. 주어진 M * N 크기의 2차원 배열 grid는 '1' 땅, '0' 물을 의미한다.
2. 주어진 2차원 크기 배열에서 섬의 개수를 반환하라.
3. gird의 외곽은 모두 물로 둘러쌓여있다고 가정한다.

 

- 1 ~ 2 : 땅(1)과 물(0)이 주어진 지도 형태의 2차원 배열 grid에 대해서 섬의 개수를 반환한다.

- 3 : grid의 최외곽은 모두 물로 둘러쌓여있다고 생각한다. 이 부분을 입출력 형태에서 살펴볼 것이다.

입출력 형태

입출력 예시

 

- 주어진 예시에서 빨간색으로 표시되어 있는 부분이 섬이다.

- 문제 3번 조건에 따라 grid의 외곽은 모두 물로 되어 있으므로 섬으로 생각할 수 있다.

- 주어진 grid를 그래프의 형태로 생각하면, 1로 연결된 정점(vertex)를 방문한 후, 1이 아닌 값으로 바꾸어, 다시는 방문하지 못하게 하여, 그래프의 1인 vertex를 모두 조회하면 1이 없는 형태로 만들면 문제를 풀 수 있을 것 같다.

풀이

class Solution:
    def dfs(self, grid: List[List[str]], i: int, j:int):
        if (i < 0 or i >= len(grid)) or \
           (j < 0 or j >= len(grid[0])) or \
           grid[i][j] == '0':
            return
        
        grid[i][j] = '0'
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)
    
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

 

- DFS를 활용하여 문제를 해결할 수 있다.

- grid를 조회하며, 땅(1)을 만났을 때, 해당 정점을 시작 정점으로 dfs를 실행한다.

- dfs에서는 i와 j가 범위를 넘어서지 않을 때, 그리고 땅이 아닌 물(0)일 경우에 종료된다.

- 그 외의 조건에서는 방문한 정점을 0으로 바꾸어 다시 방문하지 못하도록 한 후, 방문한 정점으로부터 4방위를 조회, dfs를 수행한다.

- 이렇게 할 경우 한 번의 dfs가 종료되게 되면 1개의 섬을 조회하게 되고, 해당 섬은 모두 방문했으므로 물로 처리가 되어 다시 방문하지 않는다. dfs가 종료될 경우 성공적으로 섬 1개를 조회한 것이므로, 갯수를 증가시킨다.

- 방문한 정점을 바꾸지 않을 경우, 같은 그래프에서 무한히 돌 수 있기 때문에 이 부분을 주의하여야 한다.

 

다른 풀이

DFS의 경우 위의 풀이에서 확인할 수 있듯이 재귀적(Recursive)으로 구현할 수도 있지만 스택(Stack)을 활용하여 구현할 수 있다.

스택을 활용하여 구현한 답도 공유하려고 한다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        if not grid:
            return count
        
        # stack
        stack = []
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count += 1
                    stack.append((i, j))
                    while stack:
                        _i, _j = stack.pop()
                        grid[_i][_j] = '0'
                        
                        if _i > 0  and grid[_i - 1][_j] == '1':
                            stack.append(((_i - 1), _j))
                            
                        if _i < len(grid) - 1 and grid[_i + 1][_j] == '1':
                            stack.append(((_i + 1), _j))
                            
                        if _j > 0 and grid[_i][_j - 1] == '1':
                            stack.append((_i, (_j - 1)))
                            
                        if _j < len(grid[0]) - 1 and grid[_i][_j + 1] == '1':
                            stack.append((_i, (_j + 1)))
        
        return count

 

- 스택으로 구현하는 DFS는 조건을 만족할 경우 해당 노드를 스택에 추가한다.

- 재귀적 호출에서 그러하였듯이 방문했음을 확인하기 위해 해당 노드의 값을 '0'으로 변경한다.

- 이후 방문한 노드의 4방위를 확인한다. 이 때, 양 끝단인지, 방문한 노드의 값이 '1'인지 확인한다.

- 만약, 조건을 만족한다면 스택에 집어넣는다. 이 과정을 반복하게 되면 섬 하나를 발견할 수 있다.

 

다소 코드가 길어지지만, 스택으로 작성하였을 때 훨씬 직관적으로 이해하기 쉽다고 공부하고 있는 책에서 언급했었는데, 이렇게 직접 스택으로 구현하고 나니 어떤 뜻인지 알 수 있었다.

다른 풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        def bfs(x, y):
            queue = deque([(x, y)])
            
            while queue:
                I, J = queue.popleft()
                
                for _i, _j in [I + 1, J], [I, J + 1], [I - 1, J], [I, J - 1]:
                    if 0 <= _i < len(grid) and 0 <= _j < len(grid[0]) and grid[_i][_j] == '1':
                        grid[_i][_j] = '0'
                        queue.append((_i, _j))
                        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    grid[i][j] = '0'
                    bfs(i, j)
                    count += 1
                    
        return count

 

너비 우선 탐색(BFS)을 통해서도 문제를 풀 수 있다.

BFS는 DFS와 다르게 큐를 사용하여 구현해야 한다. 문제를 푸는 방법은 DFS와 같다. 육지인 부분(1)을 만났을 때, BFS를 실행한다.

BFS 함수에서는 큐에 해당 좌표를 넣고, 해당 좌표로부터 사방위를 조회한다. 사방위가 grid의 인덱스 범위 내에 속해 있고 육지일 경우에는 조회했음을 확인하기 위해 값을 0으로 바꾸고 큐에 넣는다.

이렇게 큐에 육지들을 넣어가며 확인하면 하나의 섬을 확인할 수 있다. 이 방법을 DFS와 마찬가지로 조회하면 된다.