문제 소개
이 문제에서는 크기가 같은 두 행렬 mat1[][]과 mat2[][]가 주어집니다. 우리가 구해야 할 것은 두 행렬을 완전히 같게 만들기 위해 필요한 변환 횟수입니다.
여기서 허용되는 변환 연산은 다음과 같습니다.
- 두 행렬 중 하나를 선택합니다.
- 선택한 행렬에서 임의의 행(row) 또는 열(column) 하나를 고릅니다.
- 선택한 행 또는 열의 모든 원소에 1을 더합니다.
예제를 통해 문제를 자세히 이해해 보겠습니다.
입력
mat1[][] = {{1, 2},
{2, 1}}
mat2[][] = {{2, 3},
{4, 3}}출력
3
설명
1 2 => 2 2 => 2 3 => 2 3 2 1 => 3 1 => 3 2 => 4 3
위 과정은 다음 세 번의 변환으로 이루어집니다.
- 첫 번째 행렬의 첫 번째 행에 1을 더함 → (2, 2), (3, 1)
- 첫 번째 행렬의 두 번째 열에 1을 더함 → (2, 3), (3, 2)
- 첫 번째 행렬의 두 번째 행에 1을 더함 → (2, 3), (4, 3)
세 번의 변환 후 두 행렬이 완전히 동일해졌으므로 정답은 3입니다.
풀이 접근법
가장 기본적인 해결 방법은 변환이 가능한지 여부부터 판단하는 것입니다. 두 행렬의 차이 diff[i][j] = mat1[i][j] − mat2[i][j]를 생각했을 때, 각 칸의 차이는 반드시 '행에 더한 값'과 '열에 더한 값'의 합 형태로 표현되어야 합니다. 따라서 아래 조건을 검사합니다.
if (mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] != 0)
이 값이 0이 아니라면 어떤 변환을 사용하더라도 두 행렬을 같게 만들 수 없으므로, 이 경우 -1을 반환합니다.
반대로 변환이 가능하다면, 첫 번째 열과 첫 번째 행의 값을 기준으로 행 변환 횟수와 열 변환 횟수를 각각 계산한 뒤 모두 더하면 됩니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int countTransformationReq(int mat1[][MAX], int mat2[][MAX], int m, int n) {
// 두 행렬의 차이를 mat1에 저장
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mat1[i][j] -= mat2[i][j];
// 변환 가능 여부 검사
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
if (mat1[i][j] - mat1[i][0] - mat1[0][j] + mat1[0][0] != 0)
return -1;
// 행 변환 + 열 변환 횟수 계산
int trxCount = 0;
for (int i = 0; i < n; i++)
trxCount += abs(mat1[i][0]);
for (int j = 0; j < m; j++)
trxCount += abs(mat1[0][j] - mat1[0][0]);
return trxCount;
}
int main() {
int mat1[MAX][MAX] = { {1, 2}, {2, 1} };
int mat2[MAX][MAX] = { {2, 3}, {4, 3} };
cout << "두 행렬을 같게 만들기 위한 변환 횟수: "
<< countTransformationReq(mat1, mat2, 2, 2);
return 0;
}실행 결과
두 행렬을 같게 만들기 위한 변환 횟수: 3
복잡도 분석
이 알고리즘은 행렬의 모든 원소를 상수 번만 확인하면 되기 때문에 매우 효율적으로 동작합니다.
- 시간 복잡도: O(m × n) — 행렬의 모든 원소를 한 번씩 순회
- 공간 복잡도: O(1) — 별도의 추가 배열 없이 입력 행렬 자체를 활용
마무리
두 행렬을 같게 만드는 문제의 핵심은 '차이 행렬의 성질을 이용해 변환 가능 여부를 먼저 판별하는 것'입니다. 조건 검사식 하나로 불가능한 경우를 빠르게 걸러낼 수 있고, 가능한 경우에는 첫 행과 첫 열의 값만으로 전체 변환 횟수를 손쉽게 계산할 수 있습니다. 행렬 연산 문제에서 이처럼 구조적 특징을 활용하면 불필요한 탐색 없이 선형 시간 안에 답을 구할 수 있습니다.