JavaScript Algoritim - spiralTraversal

 

문제 설명:
2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다. 입력 받은 배열의 원소를 보시면
시계방향으로 회전하고 있으며 회전할때마다 문자열을 더해주면서 값을 만듭니다. 
이런 문제가 나오면 방향에 따른 변화와 Lookup 테이블을 만드는 것이 문제풀이에 도움이 됩니다. 

입력

인자 1 : matrix

• 세로 길이(matrix.length)가 M, 가로 길이(matrix[i].length)가 N인 2차원 배열
• matrix[i]는 string 타입을 요소로 갖는 배열
• matrix[i][j].length는 1

출력

• string 타입을 리턴해야 합니다.

주의사항

• 순회는 좌측 상단 (0,0)에서 시작합니다.
• 배열의 모든 요소를 순서대로 이어붙인 문자열을 리턴해야 합니다

 

입출력 예시

let matrix = [
  ['A', 'B', 'C'],
  ['D', 'E', 'F'],
  ['G', 'H', 'I'],
];
let output = spiralTraversal(matrix);
console.log(output); // --> 'ABCFIHGDE'

matrix = [
  ['T', 'y', 'r', 'i'],
  ['i', 's', 't', 'o'],
  ['n', 'r', 'e', 'n'],
  ['n', 'a', 'L', ' '],
];
output = spiralTraversal(matrix);
console.log(output); // --> 'Tyrion Lannister'

 

풀이코드 설명

1. 방향별로 배열을 선언 RIGHT, DOWN, LEFT, UP

2. MOVES 배열에 각 방향별로 배열을 저장
3. 가로, 세로 값을 N,M에 설정
4. 배열의 행과 열이 0이상이면서 배열 최대크기를 넘지 않도록 체크하는 isValid 선언
5. 무한반복문을 통해 방문한 곳과 아닌 곳을 구분하고 위에 설정한 방향대로 배열을 순회함

const spiralTraversal = function (matrix) {
    // 각 방향마다 row와 col의 변화를 저장
    // 원소 방향별로 오른쪽과 아래는 +1 / 왼쪽과 위는 -1 로 설정한다. 
    const RIGHT = [0, 1];
    const DOWN = [1, 0];
    const LEFT = [0, -1];
    const UP = [-1, 0];
    // 각 방향을 위한 lookup table
    const MOVES = [RIGHT, DOWN, LEFT, UP];
    //M, N에 각각 배열의 가로, 세로길이 배정 
    const M = matrix.length;
    const N = matrix[0].length;
    //행과 열이 0 이상이면서 입력받은 배열크기의 최대 크기를 넘어가지 않게 하는 것이 중요함 
    const isValid = (row, col) => row >= 0 && row < M && col >= 0 && col < N;
  
    //초기값 설정 
    let cnt = 0;
    let row = 0,
      col = -1;
    
    //방향 변수 설정 
    let direction = 0;
    //반환할 result 변수 선언 
    let result = '';
    //반복 순회조건 cnt가 M * N 미만일 때 무한 루프 
    while (cnt < M * N) {
      //룩업테이블에서 방향을 기준으로 변수 설정 
      const move = MOVES[direction];
      //move 값을 다시 rd, cd로 설정 
      //move는 [RIGHT, DOWN, LEFT, UP]; 이 값이고  더 풀어서 보면 [[0, 1], [1, 0], [0, -1], [-1, 0]];
      const [rd, cd] = move;
  
      //방향에 대한 변화값을 row, col에 저장 
      row = row + rd;
      col = col + cd;
      //isValid를 충족하면서 matrix의 원소가 false가 아닐 경우 
      while (isValid(row, col) && matrix[row][col] !== false) {
        result = result + matrix[row][col];
        // 한 요소를 두 번 접근하지 않게 하기 위해서, 접근된 요소를 false로 변경한다.
        matrix[row][col] = false;
        row = row + rd;
        col = col + cd;
        cnt++;
      }
      // row, col 이 행렬의 범위를 벗어났기 때문에,
      // 진행된 방향의 반대로 한 칸 이동한다.
      row = row - rd;
      col = col - cd;
  
      // 각 방향이 순환되기 때문에 모듈러 연산을 사용한다.
      direction = (direction + 1) % 4;
    }
    return result;
  };