알고리즘 13-2 : spiralTraversal,배열 나선형으로 순회

https://wnsdufdl.tistory.com/142

알고리즘 13 : spiralTraversal, 배열 나선형으로 순회

저번에 올린 알고리즘은 일일히 배열을 수작업으로 순회하는 알고리즘이었다.

 

이번엔 레퍼런스코드를 보고 자동화된 알고리즘을 익혔다.

---

spiralTraversal

문제

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'

 

코드

const spiralTraversal = function (matrix) {
  
  const RIGHT = [0,1];
  const DOWN = [1,0];
  const LEFT = [0,-1];
  const UP = [-1,0]

  const MOVES = [UP,DOWN,LEFT,RIGHT];
  
  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로 한다. 
  //isValid에서 오른쪽 방향만 통과하게 하려면 col의 초기값이 어떻게 되어야 하는지 생각해본다.
  let col = -1;
  
  //MOVES에서 인덱스역할을 할 direction
  let direction = 0;
  
  //순회하며 글자들을 할당할 result 문자열
  let result = '';
  
  //요소의 개수는 행렬의 넓이이다. 요소들을 다 돌면 작업을 끝낸다.
  while(cnt < M*N) {
    const move = MOVES[direction];
    const [rd,cd] = move;

    row = row+rd;
    col = col+cd;
    while(isValid(row,col) && matrix[row][col]!==false){
      result = result + matrix[row][col];

	  //지났다는 표식으로 현재 위치인 matrix[row][col]에 false를 할당한다. 
      //지나온 곳은 다시 가지 않는다.
      matrix[row][col] = false;
      row = row+rd;
      col = col+cd;
      cnt++;
    }
    //마지막까지 이르렀을때는 좌표가 배열의 길이를 초과한 상태이다. 
    //때문에 다시 뒤로 한칸씩 빼준다.
    row=row-rd;
    col=col-cd;
    
    //  각 방향이 순환되기 때문에 모듈러 연산을 사용한다.
    direction = (direction+1)%4;
  } 
  return result

};