지그재그(Zig-Zag) 방식의 행렬 출력이란?
행렬 mat[row][col]이 주어졌을 때, 아래 이미지처럼 지그재그 형태로 행렬의 모든 요소를 순서대로 출력해야 합니다. 지그재그 순회란 왼쪽 상단에서 출발하여 대각선을 따라 이동하다가 행렬의 경계에 도달할 때마다 방향을 바꾸어 나가는 방식을 말합니다.
따라서 위 행렬에 대한 출력 결과는 다음과 같습니다.
Output: 10 20 40 70 50 30 60 80 90
문제 해결 접근 방식
이 문제는 비교적 단순한 접근 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 행렬을 대각선(diagonal) 단위로 순회합니다.
- 하나의 대각선 순회가 끝날 때마다 이동 방향을 전환합니다.
- boolean 타입의 flag 변수를 사용하여 현재 진행 방향(오른쪽 위 또는 왼쪽 아래)을 추적합니다.
알고리즘
START
STEP 1 -> k = 3, l = 3 선언 및 초기화
STEP 2 -> 행렬 mat[][3] 선언
STEP 3 -> row = 0, col = 0, flag = false 선언 및 초기화
STEP 4 -> mn = MINIMUM(k, l) 설정
STEP 5 -> FOR len = 1 TO len <= mn, ++len 반복
FOR i = 0 TO i < len, ++i 반복
mat[row][col] 출력
IF i + 1 == len THEN
BREAK
END IF
IF flag THEN
row 1 증가, col 1 감소
ELSE
row 1 감소, col 1 증가
END IF
END FOR
IF len == mn THEN
BREAK
END IF
IF flag THEN
row 1 증가, flag = FALSE
ELSE
col 1 증가, flag = TRUE
END IF
END FOR
STEP 6 -> IF row == 0 THEN
IF col == k - 1 THEN
row 1 증가
ELSE
col 1 증가
END IF
flag = 1
ELSE
IF row == l - 1 THEN
col 1 증가
ELSE
row 1 증가
END IF
flag = 0
END IF
STEP 7 -> MAX = MAXIMUM(k, l) - 1 설정
STEP 8 -> FOR diag = MAX; diag > 0; --diag 반복
IF diag > mn THEN
len = mn
ELSE
len = diag
END IF
FOR i = 0 TO i < len, ++i 반복
mat[row][col] 출력
IF i + 1 == len THEN
BREAK
END IF
IF flag THEN
row 1 증가, col 1 감소
ELSE
col 1 증가, row 1 감소
END IF
IF row == 0 OR col == k - 1 THEN
IF col == k - 1 THEN
row 1 증가
ELSE
col 1 증가
END IF
flag = true
ELSE IF col == 0 OR row == l - 1 THEN
IF row == l - 1 THEN
col 1 증가
ELSE
row 1 증가
END IF
flag = false
END IF
END FOR
STOP
C 언어 구현 예제
#include <stdio.h>
#include <stdbool.h>
#define C 3
#define min(a, b) a>b?b:a
#define max(a, b) a>b?a:b
int main(){
int k = 3, l = 3;
int mat[][3] = {
{ 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 }
};
int row = 0, col = 0;
bool flag = false;
int i, j, len, diag;
int MAX;
int mn = min(k, l); // 최솟값을 구하는 매크로
for ( len = 1; len <= mn; ++len) {
for ( i = 0; i < len; ++i) {
printf("%d ", mat[row][col]); // 지그재그 형식으로 행렬 출력
if (i + 1 == len)
break;
if (flag)
++row, --col;
else
--row, ++col;
}
if (len == mn)
break;
if (flag)
++row, flag = false;
else
++col, flag = true;
}
if (row == 0) {
if (col == k - 1)
++row;
else
++col;
flag = 1;
} else {
if (row == l - 1)
++col;
else
++row;
flag = 0;
}
MAX = max(k, l) - 1; // 최댓값 확인
for ( len, diag = MAX; diag > 0; --diag) { // 대각선 방향으로 이동하는 루프
if (diag > mn)
len = mn;
else
len = diag;
for ( i = 0; i < len; ++i) {
printf("%d ", mat[row][col]);
if (i + 1 == len)
break;
if (flag)
++row, --col;
else
++col, --row;
}
if (row == 0 || col == k - 1) {
if (col == k - 1)
++row;
else
++col;
flag = true;
}
else if (col == 0 || row == l - 1) {
if (row == l - 1)
++col;
else
++row;
flag = false;
}
}
return 0;
}
실행 결과
이 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
10 20 40 70 50 30 60 80 90
마무리
이 알고리즘은 행렬의 각 요소를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(row × col)입니다. 또한 별도의 저장 공간 없이 flag 변수 하나만으로 이동 방향을 제어하기 때문에 공간 복잡도 역시 O(1)로 매우 효율적입니다. 이러한 지그재그 순회 기법은 이미지 처리, 대각선 기반 데이터 스캔 등 다양한 분야에서 폭넓게 응용될 수 있으므로, 대각선 인덱스 계산과 경계 조건 처리 로직을 잘 이해해 두는 것이 좋습니다.