[Javascript] 프로그래머스 - 빛의 경로 사이클

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

제한 사항

• 격자의 크기: 1 ≤ grid의 길이 ≤ 500
• 격자의 각 문자열의 길이: 1 ≤ grid의 각 문자열의 길이 ≤ 500
• grid의 모든 문자열의 길이는 서로 같습니다.
• grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

해결 방법

알고리즘: 구현

경로 이동 처리

• 현재 위치와 방향에서 다음 위치와 방향을 계산합니다.
• 빛이 격자 밖으로 나갈 경우, 반대쪽 끝으로 이동합니다.

방문 기록 관리

• 3차원 배열을 이용해 각 위치와 방향별로 방문 여부를 저장합니다.

사이클 길이 계산

• 방문하지 않은 경로를 시작으로 빛의 이동을 추적하여 사이클 길이를 계산합니다.
• 각 사이클의 길이를 결과 배열에 저장하고, 마지막에 오름차순으로 정렬합니다.

결과 반환

• 계산된 사이클 길이를 오름차순으로 정렬한 배열을 반환합니다.

시간 복잡도

• 격자의 크기를 n×m (행의 개수 n, 열의 개수 m)이라 할 때, 각 칸에서 4방향을 탐색하므로 최대 O(4⋅n⋅m)
• 중복된 위치는 방문하지 않으므로 모든 칸과 방향은 한 번씩만 탐색됩니다.
• 사이클 길이를 정렬하는 데 O(klog⁡k가 추가로 필요하며, k는 사이클 개수.

최종 시간 복잡도: O(n⋅m+klog⁡k)

구현 코드

function getNextPos(y, x, d, grid) {
  const moveY = [-1, 0, 1, 0];
  const moveX = [0, 1, 0, -1];
  const rows = grid.length;
  const cols = grid[0].length;

  const curY = (y + moveY[d] + rows) % rows;
  const curX = (x + moveX[d] + cols) % cols;
  let curD = d;

  if (grid[curY][curX] === "L") {
    curD = (d + 3) % 4;
  } else if (grid[curY][curX] === "R") {
    curD = (d + 1) % 4;
  }

  return { curY, curX, curD };
}

function solution(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () =>
    Array.from({ length: cols }, () => Array(4).fill(false))
  );
  const answer = [];

  for (let i = 0; i < rows; ++i) {
    for (let j = 0; j < cols; ++j) {
      for (let k = 0; k < 4; ++k) {
        if (!dp[i][j][k]) {
          dp[i][j][k] = 0;
          let y = i;
          let x = j;
          let d = k;
          let cnt = 0;

          while (!dp[y][x][d]) {
            dp[y][x][d] = true;
            cnt++;

            const { curY, curX, curD } = getNextPos(y, x, d, grid);
            y = curY;
            x = curX;
            d = curD;
          }

          answer.push(cnt);
        }
      }
    }
  }

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