이진 행렬(2차원 그리드)이 주어졌을 때, 그 안에 있는 섬의 개수를 세는 문제를 살펴보겠습니다. 여기서 섬이란 물로 둘러싸인 영역으로, 가로 또는 세로 방향으로 인접한 땅(1)들이 서로 연결되어 형성된 것을 의미합니다. 대각선 방향의 연결은 고려하지 않으며, 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정합니다.
예를 들어 다음과 같은 그리드가 있다고 가정해 보겠습니다.
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
위 그리드에는 총 3개의 섬이 존재합니다. 왼쪽 위의 2×2 크기 블록, 중앙의 단일 셀, 오른쪽 아래의 L자 형태 블록이 각각 하나의 섬입니다.
해결 접근 방식
이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 그리드를 순회하다가 값이 "1"인 셀을 발견하면, 새로운 섬을 찾은 것이므로 카운트(ans)를 1 증가시킵니다.
- 동시에 해당 셀에서 출발하여 상하좌우로 연결된 모든 땅을 "물(0)"로 바꿔 버립니다. 이렇게 하면 이미 확인한 섬을 다시 세는 중복을 방지할 수 있습니다.
알고리즘 단계
- 그리드가 비어 있으면(행의 개수가 0이면) 0을 반환합니다.
- n = 행의 개수, m = 열의 개수, ans = 0으로 초기화합니다.
- 이중 반복문으로 모든 셀을 순회하며, grid[i][j] == "1"이면 ans를 1 증가시키고 makeWater(i, j)를 호출합니다.
- makeWater() 함수는 다음과 같이 동작합니다.
- i나 j가 범위를 벗어나면(음수이거나 n, m 이상이면) 즉시 종료합니다.
- grid[i][j]가 "0"이면 종료하고, 그렇지 않으면 해당 값을 "0"으로 변경합니다.
- 상하좌우 네 방향에 대해 재귀적으로 makeWater()를 호출하여 연결된 모든 땅을 물로 만듭니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ if len(grid) == 0: return 0 n= len(grid) m = len(grid[0]) ans = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": ans+=1 self.make_water(i,j,n,m,grid) return ans def make_water(self,i,j,n,m,grid): if i<0 or j<0 or i>=n or j>=m: return if grid[i][j] == "0": return else: grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water(i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,grid)
입력
[["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]
출력
3
복잡도 분석
시간 복잡도: O(n × m) — 각 셀을 최대 한 번씩만 방문하므로 그리드의 크기에 비례합니다.
공간 복잡도: 최악의 경우 O(n × m) — 그리드 전체가 땅으로 이루어진 경우 재귀 호출 스택의 깊이가 최대가 될 수 있습니다.