Python으로 2차원 행렬에서 고유한 섬의 개수 찾기

문제 설명

2차원 이진 행렬(binary matrix)이 주어졌을 때, 행렬 안에 존재하는 서로 다른(고유한) 섬의 개수를 구하는 문제입니다. 여기서 1은 육지를, 0은 물을 나타내며, 섬이란 서로 인접해 있는 1들의 집합으로 그 둘레가 물로 둘러싸여 있는 영역을 의미합니다. 두 섬의 모양이 다르다면 서로 다른 섬으로 간주합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

이 경우 출력 결과는 4가 됩니다. 즉, 모양이 서로 다른 고유한 섬이 총 4개 존재한다는 뜻입니다.

해결 접근 방법

핵심 아이디어는 DFS(깊이 우선 탐색)를 사용해 각 섬을 탐색하면서, 섬의 시작 지점을 기준으로 한 상대 좌표(relative coordinates)를 기록하는 것입니다. 시작점 기준의 상대 좌표를 사용하면 섬의 위치와 무관하게 순수한 '모양'만 비교할 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

• dfs() 함수를 정의합니다. 이 함수는 매개변수 i, j, k, l을 받습니다. 여기서 (k, l)은 해당 섬의 시작 좌표입니다.

• mat[i][j] := 0으로 설정하여 방문 처리를 합니다.

• shape 리스트의 끝에 상대 좌표 쌍 (i − k, j − l)을 추가합니다.

• i + 1 < mat의 행 개수이고 mat[i + 1][j]가 1이면 dfs(i + 1, j, k, l)을 재귀 호출합니다.

• j + 1 < mat의 열 개수이고 mat[i][j + 1]가 1이면 dfs(i, j + 1, k, l)을 재귀 호출합니다.

• i − 1 >= 0이고 mat[i − 1][j]가 1이면 dfs(i − 1, j, k, l)을 재귀 호출합니다.

• j − 1 >= 0이고 mat[i][j − 1]가 1이면 dfs(i, j − 1, k, l)을 재귀 호출합니다.

• 메인 메소드에서는 다음을 수행합니다.

  • cnt := 0으로 초기화하고, shapes := 새로운 집합(set)을 생성합니다.

  • 행렬의 모든 칸을 이중 반복문으로 순회하면서 mat[i][j]가 1인 경우, 새로운 shape 리스트를 만들고 dfs(i, j, i, j)를 호출해 해당 섬의 모양을 기록합니다.

  • 기록된 모양이 shapes 집합에 없으면 cnt를 1 증가시키고, 해당 모양을 shapes에 추가합니다.

• 모든 탐색이 끝나면 cnt를 반환합니다.

섬의 모양을 비교할 때 위치 정보를 제거한 상대 좌표를 사용하기 때문에, 같은 모양의 섬이 행렬의 어느 위치에 있든 동일한 것으로 판별됩니다.

예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

class Solution:
   def solve(self, mat):
      def dfs(i, j, k, l):
         mat[i][j] = 0
         shape.append((i − k, j − l))
         if i + 1 < len(mat) and mat[i + 1][j]:
            dfs(i + 1, j, k, l)
         if j + 1 < len(mat[0]) and mat[i][j + 1]:
            dfs(i, j + 1, k, l)
         if i − 1 >= 0 and mat[i − 1][j]:
            dfs(i − 1, j, k, l)
         if j − 1 >= 0 and mat[i][j − 1]:
            dfs(i, j − 1, k, l)
    cnt = 0
   shapes = set()
      for i in range(len(mat)):
         for j in range(len(mat[0])):
            if mat[i][j]:
               shape = []
               dfs(i, j, i, j)
               shape = tuple(shape)
               if shape not in shapes:
                  cnt += 1
                  shapes.add(shape)
    return cnt
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

입력

[
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]

출력

4

복잡도 분석

행렬의 크기를 R × C라고 할 때, 각 칸은 최대 한 번씩만 방문되므로 시간 복잡도는 O(R × C)입니다. 공간 복잡도 역시 방문 처리를 위해 행렬 자체를 수정하고, 섬의 모양을 저장하는 데 추가 공간이 필요하므로 O(R × C)입니다.