[Algorithm] Spiral Traversal : 나선형 순회

Intro

나선형 순회에 대해서 학습한다. 처음 이 문제를 접했을 때는 이 순회가 재귀로 이루어질 수 있는지 조차에 대한 판단도 힘들었다. start 포인트와 end 포인트 처리부터 어려웠던..
손을 많이 못댔던 문제라 이번에 다시 정리한다.

Spiral Traversal : 나선형 순회

나선형 순회는 밖에서부터 안으로, 달팽이 모양처럼 요소들을 탐색하는 순회 방법이다.
총 4개의 순회 방향(right, left, down, up) 을 관리해줘야 하는 것이 핵심이며, 순회 방향마다 칸 이동을 0, 1, -1로 지정한다.
해당 문제는 입력 배열을의 모든 요소를 나선형으로 순회하며 값을 저장, 최종적으로 리턴해야 했다.
코드 요약이 어려워 수도코드와 실제 코드를 함께 기록한다.

const spiralTraversal = function (matrix) {
  // 각 방향마다 필요한 row와 col의 변화를 저장
  const RIGHT = [0, 1];
  const DOWN = [1, 0];
  const LEFT = [0, -1];
  const UP = [-1, 0];
  // 각 방향을 위한 lookup table
  const MOVES = [RIGHT, DOWN, LEFT, UP];
  const M = matrix.length;
  const N = matrix[0].length;
  const isValid = (row, col) => row >= 0 && row < M && col >= 0 && col < N;

  let cnt = 0;
  let row = 0,
    col = -1;
  let direction = 0;
  let result = '';
  
  while (count값이 M*N 값보다 작을 때까지만 실행) {
    const move = MOVES[direction]; // [[0, 1], [1, 0], [0, -1], [-1, 0]]
    const [rd, cd] = move; // right 이동 : rd 0 , cd 1

    row = row + rd; // 0 + 0
    col = col + cd; // -1 + 1
    
    // 2중 while문. 해당 turn 방향의 모든 요소를 순회
    while (isValid(row, col) && matrix[row][col] !== false) {
      result = result + matrix[row][col]; // 순회하며 그 값들을 저장
      // 한 요소를 두 번 접근하지 않게 하기 위해서, 접근된 요소를 false로 변경한다.
      matrix[row][col] = false;
      row = row + rd; // 0 + 0
      col = col + cd; // 0 + 1 , 1 + 1, 2 + 1, ...
      cnt++;
    }
    
    // row, col 이 행렬의 범위를 벗어났기 때문에, 진행된 방향의 반대로 한 칸 이동한다.
    row = row - rd;
    col = col - cd;

    // 각 방향이 순환되기 때문에 모듈러 연산을 사용한다.
    direction = (direction + 1) % 4;
  }
  return result;
};