문제 소개
2차원 행렬 M이 있다고 가정해 보겠습니다. 각 셀에는 자신의 색상을 나타내는 값이 저장되어 있으며, 상하좌우로 인접하면서 같은 색을 가진 셀들은 하나의 그룹으로 묶입니다. 여기서 '그룹에 속한 모든 셀을 특정 색상으로 한꺼번에 바꾸는' 연산을 정의합니다. 목표는 모든 셀을 같은 색으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이며, 한 번 색이 변환된 그룹은 다시는 다른 색으로 바꿀 수 없다는 제약 조건이 있습니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
| 2 | 2 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 2 | 3 | 2 | 1 |
이 경우 출력은 2입니다. 색상 2로 이루어진 그룹들을 1로 바꾼 뒤, 남아 있는 3을 1로 변경하면 전체가 같은 색이 되기 때문입니다.
접근 방법
핵심 아이디어는 깊이 우선 탐색(DFS)을 활용해 같은 색으로 연결된 영역(연결 요소)을 하나씩 찾아내고, 색상별로 그룹이 몇 개 존재하는지 세는 것입니다. 그중 그룹 수가 가장 많은 색상을 기준색으로 삼으면, 나머지 색상의 그룹 수만큼만 연산을 수행하면 됩니다.
알고리즘 단계
- 행렬이 비어 있으면 0을 반환합니다.
- dfs(i, j, matrix, val) 함수를 정의합니다.
- n은 행렬의 행 개수, m은 열 개수입니다.
- i나 j가 행렬 범위를 벗어나면 즉시 반환합니다.
- matrix[i][j]가 이미 방문 표시인 -1이면 반환합니다.
- matrix[i][j]가 val과 같다면 -1로 표시하고, 상하좌우 네 방향에 대해 재귀적으로 dfs를 호출합니다.
- 그 외의 경우에는 아무 작업 없이 반환합니다.
- 메인 로직에서는 다음을 수행합니다.
- 기본값이 0인 딕셔너리 d를 만들어 색상별 그룹 개수를 저장합니다.
- 모든 셀을 순회하면서 아직 방문하지 않은 셀(val != -1)을 만나면 d[val]을 1 증가시키고, dfs를 호출해 해당 그룹 전체를 방문 처리합니다.
- 딕셔너리 d를 값 기준으로 오름차순 정렬한 리스트 l을 만들고, 마지막 원소(그룹 수가 가장 많은 색상)를 safe로 지정합니다.
- safe가 아닌 색상의 그룹 개수를 모두 더한 값을 res로 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
class Solution:
def solve(self, matrix):
if not matrix:
return 0
def dfs(i, j, matrix, val):
n, m = len(matrix), len(matrix[0])
if i < 0 or i > n - 1 or j < 0 or j > m - 1:
return
if matrix[i][j] == -1:
return
if matrix[i][j] == val:
matrix[i][j] = -1
dfs(i, j + 1, matrix, val)
dfs(i + 1, j, matrix, val)
dfs(i, j - 1, matrix, val)
dfs(i - 1, j, matrix, val)
else:
return
n, m = len(matrix), len(matrix[0])
d = defaultdict(int)
for i in range(n):
for j in range(m):
val = matrix[i][j]
if val != -1:
d[val] += 1
dfs(i, j, matrix, val)
l = sorted(d, key=lambda x: d[x])
safe = l[-1]
res = 0
for k, v in d.items():
if k != safe:
res += v
return res
ob = Solution()
matrix = [
[2, 2, 2, 2],
[1, 1, 1, 1],
[2, 3, 2, 1]
]
print(ob.solve(matrix))
입력
matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]
출력
2
복잡도 분석
각 셀은 DFS 과정에서 정확히 한 번씩 방문 처리되므로 시간 복잡도는 O(n×m)입니다. 공간 복잡도 역시 재귀 호출 스택과 색상별 그룹 정보를 저장하는 딕셔너리를 고려하면 O(n×m)입니다.