[JS / 알고리즘] spiralTraversal

드림보이즈·2023년 2월 25일

문제 :

2차원 M x N 배열을 나선형으로 순회하고, 연결된 값을 리턴하라

주의사항 :

순회는 좌측 상단 (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'

핵심 포인트 :

Q. 범위를 벗어났을 때, 이미 방문했을 때 어떻게 할 것인가?

A. isValid(row,col) 만들어라, 이미 방문했으면 그 점의 문자열을 false로 바꿔라

Q. 방향 전환하는 순서가 정해져 있다. 이를 어떻게 구현할 것인가?

MOVES = [RIGHT,DOWN,LEFT,UP]으로 해둔다. (각 방향마다 row,col 세팅해둔 채)

Q. 모든 점을 방문했는지 어떻게 체크할 것인가?

A. M X N 만큼 방문할 때 마다 카운팅을 while문으로 돌린다.

Q. 움직이는 방향이 변한다면 그것을 어떻게 구현할 것인가?

MOVES = [RIGHT,DOWN,LEFT,UP];
direction = 0;

move = MOVES[0];

으로 해두다가 방향 전환이 필요한 경우

direction = (direction + 1) % 4;

를 이용해 다음 방향으로 설정을 할 수 있다.




function spiralTraversal(matrix) {
  // 1. 방향마다 row, col 변화를 미리 선언
  const RIGHT = [0,1];
  const DOWN = [1,0];
  const LEFT = [0,-1];
  const UP = [-1,0];
  
  // 2. 움직이는 순서 미리 세팅, 전체 길이, 범위 내부에서 움직이게 세팅
  
  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;
  
  // 3. 기타 세팅 (움직이는 방향 / 몇 번 움직였는지 / 최초 위치)
  
  // 전체 돌아야 하니 카운트 할 변수 필요
  let cnt = 0;
  
  // 아직 움직이기 전이니까 움직였을 때 0,0으로 가게 하는 곳에 초기값 세팅
  let row = 0, col = -1;
  
  // 움직이는 방향
  let direction = 0;
  
  // 리턴할 문자열
  let result = "";
  
  // 모든 점 다 돌 때 까지 반복
  while(cnt < M * N ) {
    
    // 처음엔 right니 0,1이겠지
    const move = MOVES[direction];
    
    // 다음 위치에 써야 하니 따로 빼두고
    const [rd, cd] = move;
    
    // 최초 위치가 0,-1이니까 처음 시작위치로 움직이자
    row = row + rd;
    col = col + cd;
    
    // 범위 안 넘어가고 & 처음 온 곳이면
    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 = row - rd;
  col = col - cd;
  
  direction = (direction + 1 ) % 4;
  
  }

return result;
}