C++로 주어진 행렬이 '좋은 행렬'인지 판별하는 방법

문제 소개

n × n 크기의 행렬이 하나 주어집니다. 이 행렬 속 1이 아닌 모든 숫자가 자신과 같은 행에 있는 어떤 수와 같은 열에 있는 어떤 수의 합으로 표현될 수 있을 때, 그 행렬을 '좋은(good) 행렬'이라고 부릅니다. 이 글에서는 주어진 행렬이 좋은 행렬인지 여부를 판별하는 C++ 코드를 살펴보겠습니다.

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

이 경우 출력은 True입니다. 왼쪽 아래 모서리의 6은 바로 위에 있는 2와 오른쪽에 있는 4의 합(2 + 4 = 6)이므로 조건을 충족하기 때문입니다. 이 행렬에서 1이 아닌 나머지 숫자들 역시 모두 같은 조건을 만족합니다.

풀이 접근 방식

이 문제는 브루트 포스(완전 탐색) 기법으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

• 행렬의 모든 칸 (i, j)를 차례대로 검사합니다.
• 현재 칸의 값이 1이면 검사 대상이 아니므로 그대로 통과시킵니다.
• 값이 1이 아니라면 그 값을 c에 저장한 뒤, 같은 행의 모든 원소 M[i][h]와 같은 열의 모든 원소 M[k][j]를 서로 짝지어 더해 봅니다.
• 두 수의 합이 c와 일치하는 조합이 하나라도 존재하면 해당 칸은 유효하며, ok 플래그를 1로 설정합니다.
• 모든 조합을 확인한 후에도 ok가 0이라면 그 행렬은 좋은 행렬이 아니므로 즉시 false를 반환합니다.

모든 칸이 검사를 통과하면 최종적으로 true를 반환합니다. 각 칸마다 행과 열의 모든 조합을 확인하므로 시간 복잡도는 O(n⁴)입니다.

알고리즘 의사 코드

n := M의 크기
for i := 0 to n-1:
    for j := 0 to n-1:
        ok := 0
        if M[i][j] != 1:
            c := M[i][j]
        for h := 0 to n-1:
            for k := 0 to n-1:
                if c == M[i][h] + M[k][j]:
                    ok := 1
        if ok == 0 and M[i][j] != 1:
            return false
return true

C++ 구현 예제

아래 예제를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> M){
    int n = M.size();
    int c;
    bool ok;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            ok = 0;
            if (M[i][j] != 1)
                c = M[i][j];
            for (int h = 0; h < n; h++){
                for (int k = 0; k < n; k++)
                    if (c == M[i][h] + M[k][j])
                        ok = 1;
            }
            if (ok == 0 && M[i][j] != 1){
                return false;
            }
        }
    }
    return true;
}
int main(){
    vector<vector<int>> matrix = { { 1, 1, 2 }, { 2, 3, 1 }, { 6, 4, 1 } };
    cout << solve(matrix) << endl;
}

실행 결과

입력:

{ { 1, 1, 2 }, { 2, 3, 1 }, { 6, 4, 1 } }

출력:

1

solve() 함수가 true(1)를 반환했으므로, 주어진 행렬은 좋은 행렬의 조건을 만족한다는 것을 확인할 수 있습니다.