[프로그래머스] 빛의 경로 사이클 with JavaScript

📌 문제

https://school.programmers.co.kr/learn/courses/30/lessons/86052

📌 풀이

그래프 문제가 나왔을 떄 나는 보통 BFS를 이용해서 풀기 때문에 BFS로 생각해서 풀었다.

1. 먼저 상하좌우 방향과 기본 그래프 2차원 배열 두개를 생각해서 3차원 배열로 만든다.
2. 방문하지 않은 좌표(x, y, d:방향)에 있을 경우 그 좌표로부터 방문한 길이(루트)를 측정하기 위해 BFS를 사용한다.
3. queue에 [[x, y, d, 0]] 길이(0으로)까지 넣어서 방문하지 않았다면 다음 좌표로 이동하는 순서로 구현한다.
   • 여기서 다음 좌표로 이동할 때 move함수와 rotate함수를 사용해서 이동하였다.
4. 그리고 방문했던 좌표가 되었을 때 길이를 return해준다.
5. 모든 좌표를 계산했다면 결과를 오름차순으로 정렬해서 반환한다.

📌 내 코드

const RIGHT = 'R';
const LEFT = 'L';
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

function solution(grid) {
  const answer = [];
  const [N, M] = [grid.length, grid[0].length];
  const visited = Array.from(Array(N), () => Array.from(Array(M), () => Array(4).fill(false)));

  const move = (x, y, direction) => {
    let nx = x + dx[direction];
    let ny = y + dy[direction];

    if (nx < 0) nx = N - 1;
    if (nx === N) nx = 0;
    if (ny < 0) ny = M - 1;
    if (ny === M) ny = 0;

    return [nx, ny];
  };

  const rotate = (location, direction) => {
    if (location === LEFT) return [2, 3, 1, 0][direction];
    if (location === RIGHT) return [3, 2, 0, 1][direction];
    return direction;
  };

  const getLengthInCycle = (x, y, d) => {
    const queue = [[x, y, d, 0]];

    while (queue.length) {
      const [x, y, d, len] = queue.shift();

      if (visited[x][y][d]) {
        answer.push(len);
        return;
      }
      visited[x][y][d] = true;

      let [nx, ny] = move(x, y, d);
      let nd = rotate(grid[nx][ny], d);

      queue.push([nx, ny, nd, len + 1]);
    }
  };

  for (let x = 0; x < N; x++) {
    for (let y = 0; y < M; y++) {
      for (let direction = 0; direction < 4; direction++) {
        if (!visited[x][y][direction]) {
          getLengthInCycle(x, y, direction);
        }
      }
    }
  }

  return answer.sort((a, b) => a - b);
}

console.log(solution(['SL', 'LR'], [16])); // [16] 
console.log(solution(['S'], [1, 1, 1, 1])); // [1, 1, 1, 1] 
console.log(solution(['R', 'R'], [4, 4])); // [4, 4] 

🔥 느낀점

그래프 문제였음에도 낯설게 느껴질 정도로 잘 낸 문제라고 생각한다. 아무래도 오랜만에 그래프 문제를 풀 다 보니 많이 헤맸다. 시간 안에 다 풀지 못해서 매우 속상했다.