JavaScript로 행렬 대각선 순회하기: 지그재그 탐색 구현 가이드

문제 정의

정방 행렬(행과 열의 개수가 같은 배열의 배열)을 입력받아, 행렬을 대각선 방향으로 지그재그 형태로 순회하면서 그 과정에서 만난 요소들을 순서대로 새로운 배열에 담아 반환하는 JavaScript 함수를 작성해야 합니다.

예를 들어, 함수에 다음과 같은 3×3 행렬이 주어진 경우를 생각해 보겠습니다.

const arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

이때 기대되는 출력 결과는 다음과 같습니다.

const output = [1, 2, 4, 7, 5, 3, 6, 8, 9];

순회는 첫 번째 대각선에서 오른쪽 위(↗) 방향으로 시작하여, 다음 대각선에서는 왼쪽 아래(↙) 방향으로 진행되는 식으로 방향을 번갈아 바꿔가며 이루어집니다.

구현 코드

const arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];
const findDiagonalOrder = (arr = []) => {
  if(!arr.length){
    return [];
  };
  let ind = 0;
  let colBegin = 0, rowBegin = 0;
  let rowMax = arr.length, colMax = arr[0].length;
  const res = [], stack = [];
  while(rowBegin < rowMax || colBegin < colMax) {
    for(let row = rowBegin, col = colBegin; row < rowMax && col >= 0;
    row++, col--){
      if(ind % 2 === 0){
        stack.push((arr[row][col]));
      }else{
        res.push(arr[row][col]);
      };
    };
    ind++;
    while(stack.length){
      res.push(stack.pop());
    };
    colBegin++
    if(colBegin > colMax-1 && rowBegin < rowMax){
      colBegin = colMax-1
      rowBegin++
    }
  };
  return res
};
console.log(findDiagonalOrder(arr));

코드 동작 원리

위 코드의 핵심 로직을 단계별로 정리하면 다음과 같습니다.

시작점 추적 및 단방향 순회: 각 대각선을 따라 한 방향으로 이동하며, 현재 대각선의 시작 위치(rowBegin, colBegin)를 계속 추적합니다.
짝수 인덱스에서 스택 활용: 대각선 번호(ind)가 짝수일 때는 요소를 스택에 임시로 저장(push)하고, 해당 대각선의 끝에 도달하면 차례로 꺼내(pop) 결과 배열에 추가합니다. 덕분에 순서가 뒤집혀 반대 방향 순회가 자연스럽게 구현됩니다.
인덱스 증가로 방향 전환: 다음 대각선으로 넘어갈 때마다 ind 값을 1씩 증가시켜, 짝수·홀수 여부에 따라 순회 방향을 번갈아 전환합니다.
열 우선, 이후 행 이동: 열 시작 인덱스(colBegin)를 먼저 끝까지 증가시키고, 마지막 열에 도달한 이후에는 colBegin을 마지막 열에 고정한 채 행 시작 인덱스(rowBegin)를 증가시키며 남은 대각선을 순회합니다.

실행 결과

코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

[
  1, 2, 4, 7, 5,
  3, 6, 8, 9
]

복잡도 분석

이 알고리즘은 행렬의 모든 요소를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n × m)입니다. 공간 복잡도는 결과 배열을 제외하면 가장 긴 대각선의 길이만큼 스택을 사용하므로 O(min(n, m))입니다.