[JS]알고리즘 문제풀이 13

spiral Traversal : 행렬형태로 되어있는 이중 배열을 나선형으로 한바퀴 돌면서 요소들을 출력하는 알고리즘 문제

 

위의 그림과 같이 회전 시마다 1. 오른쪽 -> 2. 아래로 -> 3. 왼쪽으로 -> 4. 위로 해당 순서로, 한바퀴 돌면서, 각 요소들을 제거하고 새로운 배열에 집어넣어준다. 

그렇다면 그 다음 회전시에는 2번째 회전 이후에 보이는 예시처럼 새로운 행렬에서 새로 한바퀴 도는 형태가 된다. 

 

var spiralTraversal = function (matrix) {
  var result = [];
  var goAround = function (matrix) {
    //매트릭스 내에 원소가 하나도 없는 경우가 재귀함수 나오는 기저조건
 
    // 나선형으로 돌려면 행렬 기준으로 가장 바깥의 원소들을 한바퀴 돌아야 한다.
    // 주어진 행렬의 가장 첫번째 배열을 그냥 통째로 제거하고 새로운 배열에 넣으면 일종의 왼쪽에서 오른쪽으로 한바퀴 돌면서 원소를 하나씩 넣은 격이다.
    //따라서 따로 반복문을 돌지 않고, 배열 하나를 통째로 concat으로 결과 배열과 합쳐주고 shift로 기존 행렬에서는 제거해준다.
    if (matrix.length !== 0) {
      result = result.concat(matrix.shift());
    } else {
      return;
    }
 
    // 아래로 내려 가는 경우이다.
    // 행렬의 j번째에 위치한 배열의 가장 마지막 요소를 제거하여 결과 배열에 넣어준다. 따라서 pop활용한다.
    for (var j = 0; j < matrix.length - 1; j++) {
      if (matrix[j].lenth !== 0) {
        result.push(matrix[j].pop());
      } else {
        return;
      }
    }
 
    // 가장 아래에서 오른쪽-> 왼쪽으로 가는 경우는 첫번째 경우인 가장 첫번쩌 배열에서 왼쪽-> 오른쪽으로 가는 경우를 반대로 생각하면 된다.
    //주어진 행렬의 가장 마지막 배열을 넣어주되(pop사용), 이번엔 오른쪽-> 왼쪽으로 가는 것이기 때문에 reverse로 뒤집어 준다.
    if (matrix.length !== 0) {
      result = result.concat(matrix.pop().reverse());
    } else {
      return;
    }
 
    // 이 또한 아래로 내려가는 경우와 반대로 생각하면된다.
    // 이번에는 k번째 배열의 가장 맨 앞의 요소가 제거되면서 결과 배열에 들어가야 한다.
    for (var k = matrix.length - 1; k >= 0; k--) {
      if (matrix[k].length !== 0) {
        result.push(matrix[k].shift());
      } else {
        return;
      }
    }
    //이렇게 재귀함수를 돌다가 가장 맨위의 기저조건 즉 행렬에 요소가 하나도 없을때까지 돌다가 반환된다.
    return goAround(matrix);
  };
 
  goAround(matrix);
 
  return result;
};