Toy 문제 23

문제

2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다.

 

입력

인자 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'

 

수도코드(해석)

말판같은 문제들은 기본적으로 움직이는 값들을 먼저 선언, 설정해주고(right, down, left, up)

말판 밖으로 나가지 않게 하기위한 함수를 설정해줍니다 (isValid)

그리고 현재의 위치를 나타내어주는 x,y 값을 선언해주고, 다녀 왔던곳은 false로 값을 바꾸어 줍니다.

 

말판 이동문제가 대부분 비슷하게 느껴지는데 여기서 새로운 것을 안 부분은

direction = (direction + 1) % 4; 코드를 사용하는 부분이고,

 

direction이 0으로 시작하고 direction[0] 처음부분이 Right이므로 while안에 while문이 계속 반복해주면서 반복문이 끝나 Right 의 역할을 다 했을 때

+1을 시켜주어서 그다음인 Down을 실행시켜 주는 것입니다. 이렇게 오른쪽 아래 왼쪽 위 를 계속해서 반복해 주는 것입니다.

그 외 내용은 주석을 달아 놓았습니다.

 

코드(Reference)

const spiralTraversal = function (matrix) {
  // 방향키설정
  const RIGHT = [0, 1];
  const DOWN = [1, 0];
  const LEFT = [0, -1];
  const UP = [-1, 0];
  //나선형이동을 위한 RDLU 배치
  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 row = 0,
    col = -1; // 시작할때, 밖에서 시작하도록하여 A값을 포함시키기 위해서
  let direction = 0;
  let result = '';

 //문자열 결과값이 말판의 넓이(모든글자)와 같아지면 반복문 중지
  while (result.length < M * N) {

    //방향키 값 가져오기
    const [rd, cd] = MOVES[direction];

    //방향키만큼 현재위치에서 방향키값 더해서 이동
    row = row + rd;
    col = col + cd;
    

    //말판 밖으로 나가거나, 말판 안의 false를 만날때 까지 반복
    while (isValid(row, col) && matrix[row][col] !== false) {
      result += matrix[row][col];
      // 한 요소를 두 번 접근하지 않게 하기 위해서, 접근된 요소를 false로 변경한다.
      matrix[row][col] = false;
      row = row + rd;
      col = col + cd;
    }


    // row, col 이 행렬의 범위를 벗어났기 때문에,
    // 진행된 방향의 반대로 한 칸 이동한다.
    row = row - rd;
    col = col - cd;

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

  }
  return result;
};