C++로 쌍대칭 행렬(Bisymmetric Matrix) 판별하기

이번 글에서는 주어진 행렬이 쌍대칭 행렬(Bisymmetric Matrix)인지 판별하는 프로그램을 살펴보겠습니다.

쌍대칭 행렬이란 두 개의 대각선, 즉 주대각선(왼쪽 위 → 오른쪽 아래)과 부대각선(오른쪽 위 → 왼쪽 아래)을 기준으로 모두 대칭인 정사각 행렬을 의미합니다. 다음 행렬이 쌍대칭 행렬의 대표적인 예시입니다.

1 2 3 4 5
2 6 7 8 4
3 7 9 7 3
4 8 7 6 2
5 4 3 2 1

알고리즘

checkBiSymmetric(mat, n)

쌍대칭 여부를 확인하는 절차는 크게 두 단계로 나뉩니다.

1. 주대각선 대칭 검사: 일반적인 대칭 행렬 조건과 동일하게, mat[i][j]와 mat[j][i]가 모두 같은지 확인합니다.
2. 부대각선 대칭 검사: mat[i][j]와 mat[n-j-1][n-i-1]이 같은지 확인하여 반대 방향 대각선 기준의 대칭성을 검증합니다.

Begin
   for i in range 0 to n – 1, do
      for j in range 0 to i – 1, do
         if mat[i, j] is not same as mat[j, i], then
            return false
         end if
      done
   done
   for i in range 0 to n – 1, do
      for j in range 0 to n – i, do
         if mat[i, j] is not same as mat[n – j - 1, n – i - 1], then
            return false
         end if
      done
   done
   return true
End

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. 첫 번째 반복문에서 주대각선 기준 대칭을 검사하고, 두 번째 반복문에서 부대각선 기준 대칭을 검사합니다. 하나라도 조건을 만족하지 않으면 즉시 false를 반환합니다.

#include<iostream>
#define N 5
using namespace std;
int matrix[N][N] = {{1, 2, 3, 4, 5},
{2, 6, 7, 8, 4},
{3, 7, 9, 7, 3},
{4, 8, 7, 6, 2},
{5, 4, 3, 2, 1}};
bool checkBiSymmetric() {
   // 주대각선 기준 대칭 검사
   for (int i = 0; i < N; i++)
      for (int j = 0; j < i; j++)
         if (matrix[i][j] != matrix[j][i]) // 대응하는 요소가 다르면 false 반환
            return false;
   // 부대각선 기준 대칭 검사
   for (int i = 0; i < N; i++)
      for (int j = 0; j < N - i; j++)
         if (matrix[i][j] != matrix[N - j - 1][N - i - 1]) // 대응하는 요소가 다르면 false 반환
            return false;
   return true; // 모든 조건을 만족하면 true 반환
}
main() {
   if(checkBiSymmetric()){
      cout << "Yes the matrix is bisymmetric";
   } else {
      cout << "No the matrix is not bisymmetric";
   }
}

실행 결과

Yes the matrix is bisymmetric

예제 행렬은 두 대각선 모두에 대해 대칭이므로, 프로그램은 해당 행렬이 쌍대칭 행렬임을 올바르게 판별합니다. 이 방식은 시간 복잡도 O(n²)으로 간단하고 효율적으로 동작합니다.