문제 이해하기
이 문제에서는 2차원 행렬(matrix)이 주어지며, 우리의 과제는 행렬의 모든 요소를 대각선 순서로 출력하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
1 2 3 4 5 6 7 8 9
출력 결과 −
1 4 2 7 5 3 8 6 9
위 출력에서 볼 수 있듯이, 행렬의 요소들이 왼쪽 아래에서 오른쪽 위로 향하는 대각선 방향으로 지그재그 형태로 출력되는 것을 확인할 수 있습니다.
대각선 순회의 패턴 분석
행렬을 지그재그 또는 대각선 형태로 출력할 때 따라야 하는 패턴을 살펴보겠습니다.
위 그림이 바로 대각선 순회(diagonal traversal)가 작동하는 방식입니다.
출력되는 라인의 개수는 항상 2차원 행렬의 행(row)과 열(column)의 크기에 의해 결정됩니다.
즉, 2차원 행렬 mat[r][c]에 대해 출력 라인의 총 개수는 r + c − 1개가 됩니다.
구현 예제
이제 C++로 작성된 실제 솔루션 코드를 살펴보겠습니다.
#include <iostream>
using namespace std;
#define R 5
#define C 4
int min2(int a, int b)
{ return (a < b)? a: b; }
int min3(int a, int b, int c)
{ return min2(min2(a, b), c);}
int max(int a, int b)
{ return (a > b)? a: b; }
void printDiagonalMatrix(int matrix[][C]){
for (int line=1; line<=(R + C -1); line++){
int start_col = max(0, line-R);
int count = min3(line, (C-start_col), R);
for (int j=0; j<count; j++)
cout<<matrix[min2(R, line)-j-1][start_col+j]<<"\t";
cout<<endl;
}
}
int main(){
int M[R][C] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16},
{17, 18, 19, 20}};
cout<<"The matrix is : \n";
for (int i=0; i< R; i++){
for (int j=0; j<C; j++)
cout<<M[i][j]<<"\t";
cout<<endl;
}
cout<<"\nZigZag (diagnoal) traversal of matrix is :\n";
printDiagonalMatrix(M);
return 0;
}
실행 결과
The matrix is : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ZigZag (diagonal) traversal of matrix is : 1 5 2 9 6 3 13 10 7 4 17 14 11 8 18 15 12 19 16 20
코드 동작 원리 정리
핵심 로직을 간단히 정리하면 다음과 같습니다.
1. 라인 반복: 전체 대각선 라인의 개수는 R + C − 1이므로, line 변수를 1부터 R + C − 1까지 반복합니다.
2. 시작 열 계산: 각 라인에서 출력을 시작할 열(start_col)은 max(0, line − R)로 계산합니다. 행의 개수보다 라인 번호가 커지는 시점부터 시작 열이 오른쪽으로 이동하기 때문입니다.
3. 요소 개수 계산: 해당 라인에 포함되는 요소의 개수(count)는 line, (C − start_col), R 중 최솟값으로 결정됩니다.
4. 역방향 인덱싱: 각 대각선은 왼쪽 아래에서 오른쪽 위 방향으로 진행되므로, 행 인덱스는 감소하고(min2(R, line) − j − 1) 열 인덱스는 증가(start_col + j)하며 요소를 출력합니다.
이 알고리즘의 시간 복잡도는 O(R × C)로, 행렬의 모든 요소를 정확히 한 번씩만 방문하므로 매우 효율적입니다.