프로그래머스 - 빛의 경로 사이클 (자바스크립트)

빛의 경로 사이클

프로그래머스 1, 2레벨 문제를 모두 풀어보기로 결심하고 두 달이 지났다.
오늘 마지막 문제를 풀이했는데 삽질 회고 겸 내가 시도한 접근 방식을 기록하기로 함

입력으로 1차원 배열 grid가 들어오는데 배열의 요소로 "S", "L", "R"으로 이루어진 문자열이 들어있다.

"S"는 빛의 방향을 계속 유지시키고
"L"은 좌회전,
"R"은 우회전 시킨다.

빛은 모든 칸에서, 모든 방향으로 출발할 수 있다. 이때 빛이 이동할 수 있는 모든 사이클의 길이를 구하고 그 길이를 오름차순으로 정렬해 반환하면 된다.

먼저 빛이 이동할 수 있는 방향은 상하좌우로 네 방향으로 되어 있어, 빛이 이동할 다음 좌표를 구하기 위한 좌표 배열을 선언했다. (dx, dy)

빛은 도착한 칸의 문자에 따라 다른 방향으로 뻗어 갈 수 있는데 이미 방문한 방향으로 확인되면 하나의 사이클이 완성되는 것이기 때문에, 탐색 종료 조건을 체크하기 위한 체크 배열을 선언하고 값을 [0, 0, 0, 0](상하좌우)로 초기화했다. (ch)

이제 grid의 요소를 하나씩 순회하며 빛이 출발하지 않은 방향이 있는 경우 사이클을 구하는 함수(checker)를 호출하고 반환된 사이클의 길이가 0 이상인 경우 answer에 추가한다.

checker는 빛이 이미 방문한 적이 있었던 방향이 나올 때까지 반복하며 다음 좌표로 이동시킨다.
처음 방문하는 방향이라면 체크 배열에 값을 체크한다.
다음 좌표를 구하기 위해 빛이 향해야 할 방향을 함수(getNextDir)를 통해 구한다.

getNextDir는 칸의 문자에 따라 "S" 직진, "L" 좌회전, "R" 우회전할 수 있도록 방향 정보를 반환한다. 반환되는 값은 0, 1, 2, 3으로 각각 상하좌우를 의미한다.

모든 grid 좌표와 방향에 대한 사이클 탐색이 종료되면 answer를 오름차순 정렬해 반환하면 끝!

function solution(grid) {
  const answer = [];

  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];

  const ch = Array.from({ length: grid.length }, () => []).map((c) => {
    for (let i = 0; i < grid[0].length; i++) c.push([0, 0, 0, 0]);
    return c;
  });

  for (let x = 0; x < grid.length; x++) {
    for (let y = 0; y < grid[0].length; y++) {
      for (let d = 0; d < dx.length; d++) {
        if (ch[x][y][d]) continue;
        const cnt = checker(x, y, d);
        if (cnt) answer.push(cnt);
      }
    }
  }

  function checker(x, y, d) {
    let cnt = 0;
    while (true) {
      if (ch[x][y][d]) break;
      ch[x][y][d] = 1;
      cnt++;

      x = x + dx[d];
      y = y + dy[d];
      if (x < 0) x = grid.length - 1;
      if (x >= grid.length) x = 0;
      if (y < 0) y = grid[0].length - 1;
      if (y >= grid[0].length) y = 0;
      d = getNextDir(grid[x][y], d);
    }
    return cnt;
  }

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

function getNextDir(block, dir) {
  if (block === "S") return dir;
  if (block === "L") return [2, 3, 1, 0][dir];
  if (block === "R") return [3, 2, 0, 1][dir];
}

효율성은 개선이 필요하다.. ㅎㅎ

한 가지 의문인 점은 checker 함수 while문 안의 로직을 똑같이 가져와 DFS 재귀로 리팩토링해 돌려보니 특정 테스트 케이스만 런타임 에러가 뜬다. 몬가 잘못한 거겠지 😢 다시 확인해 볼 부분

하반기를 시작으로 넉넉하게 올해 말까지 생각한 챌린지를 끝내니 후련하다.
이어서 3레벨 문제를 풀이하기엔 머리 아플 것 같고 🙄 당분간 다른 플랫폼의 비슷한 레벨의 문제를 풀거나 기존 풀이를 효율적으로 고쳐볼 생각이다.

끗~~~