2차원 그리드에 여러 개의 0(물)과 1(땅)이 있을 때, 섬의 개수를 세는 문제를 파이썬으로 해결하는 방법을 알아보겠습니다. 여기서 섬(island)이란 물로 둘러싸여 있으며, 가로 또는 세로 방향으로 인접한 땅들이 서로 연결되어 형성된 영역을 의미합니다. 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정합니다.
문제 예시
다음과 같은 그리드가 있다고 가정해 보겠습니다.
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
위 그리드에서 색칠된 영역들을 보면 총 3개의 섬이 존재합니다.
해결 접근 방식
이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 개의 메서드를 사용합니다. 섬의 개수를 세는
numIslands()와, 발견한 섬을 물로 바꾸어 중복 카운트를 방지하는makeWater()입니다. - 그리드의 행 수가 0이면 즉시 0을 반환합니다.
- n은 행(row)의 개수, m은 열(column)의 개수, ans는 섬의 개수를 저장하는 변수입니다.
- 이중 반복문으로 그리드의 모든 칸을 순회하며 값이 '1'인 칸을 발견하면 ans를 1 증가시키고, 해당 위치에서
makeWater()를 호출해 연결된 모든 땅을 물('0')로 변경합니다.
makeWater() 메서드의 동작 순서는 다음과 같습니다.
- 인덱스 i, j가 그리드 범위를 벗어나면(i < 0 또는 j < 0 또는 i ≥ n 또는 j ≥ m) 메서드를 종료합니다.
- 현재 칸의 값이 '0'(물)이면 종료하고, 그렇지 않으면 해당 칸을 '0'으로 변경합니다.
- 상, 하, 좌, 우 네 방향에 대해 재귀적으로
makeWater()를 호출하여 인접한 땅을 모두 물로 만듭니다.
이렇게 하면 하나의 섬에 속한 모든 땅이 한 번만 카운트되므로 정확한 섬의 개수를 구할 수 있습니다.
구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
class Solution(object):
def numIslands(self, grid):
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)
ob1 = Solution()
print(ob1.numIslands([["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]))입력
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
출력
3
마무리
이 알고리즘의 시간 복잡도는 O(n × m)으로, 그리드의 모든 칸을 최대 한 번씩만 방문하기 때문에 매우 효율적입니다. DFS 대신 BFS(너비 우선 탐색)나 Union-Find 자료구조를 활용해서도 동일한 문제를 해결할 수 있으니, 관심 있는 분들은 추가로 학습해 보시길 권장합니다.