C#으로 주어진 행렬이 토플리츠(Toeplitz) 행렬인지 확인하는 방법

행렬에서 왼쪽 위에서 오른쪽 아래로 내려가는 모든 대각선에 같은 요소들이 있을 때, 이 행렬을 토플리츠(Toeplitz) 행렬이라고 합니다. 즉, 각 대각선을 따라 값이 일정하게 유지되어야 한다는 의미입니다.

예제 1

[[1,2,3,4],
[5,1,2,3],
[9,5,1,2]]

출력 결과 −

true

위 행렬의 대각선 요소들을 살펴보면 다음과 같습니다.

"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".

모든 대각선에 포함된 요소들이 각각 동일하므로, 이 행렬은 토플리츠 행렬입니다. 따라서 결과는 true입니다.

예제 2

입력 행렬:
[[1,2],
[2,2]]

출력 결과 −

false

이 경우 대각선 "[1, 2]"에 서로 다른 요소가 포함되어 있으므로 토플리츠 행렬이 아니며, 결과는 false입니다.

C# 구현 코드

토플리츠 행렬 여부를 확인하는 알고리즘은 매우 간단합니다. 두 번째 행·열부터 시작하여 현재 위치의 값 mat[i, j]가 바로 왼쪽 위 대각선 값 mat[i-1, j-1]과 같은지 비교합니다. 하나라도 다른 값이 발견되면 즉시 false를 반환하고, 모든 비교를 통과하면 true를 반환합니다.

public class Matrix
{
    public bool ToeplitzMatrix(int[] mat)
    {
        int row = getMatrixRowSize(mat);
        int col = getMatrixColSize(mat);
        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < col; j++)
            {
                if (mat[i, j] != mat[i - 1, j - 1])
                {
                    return false;
                }
            }
        }
        return true;
    }
    private int getMatrixRowSize(int[] mat)
    {
        return mat.GetLength(0);
    }
    private int getMatrixColSize(int[] mat)
    {
        return mat.GetLength(1);
    }
}
static void Main(string[] args)
{
    Matrix m = new Matrix();
    int[] mat = new int[3, 4] { { 1, 2, 3, 4 }, { 5, 1, 2, 3 }, { 9, 5, 1, 2 } };
    Console.WriteLine(m.ToeplitzMatrix(mat));
}

실행 결과

True

위 예제에서 입력 행렬은 모든 대각선의 요소가 동일하므로, 프로그램은 True를 출력하며 해당 행렬이 토플리츠 행렬임을 확인할 수 있습니다. 이 방법의 시간 복잡도는 O(row × col)로, 행렬의 모든 요소를 한 번씩만 검사하기 때문에 효율적입니다.