백준 14891번 - 톱니바퀴 (JS)

문제 설명

1. 톱니 8개를 가진 톱니바퀴 4개가 일자로 붙어있다. 톱니는 N극(0) 또는 S극(1)을 가지고 있다.

2. 톱니바퀴 하나를 톱니 한 칸 만큼 시계 방향(1) 혹은 반시계 방향(-1)으로 회전시킨다.

3. 붙어있는 톱니바퀴 A와 B가 회전하는 경우의 수는 다음과 같다.
   a. A와 B 모두 회전 → A가 회전하고, A와 B의 맞닿은 극이 다를 경우
   b. A만 회전, B는 회전 X → A가 회전하고, A와 B의 맞닿은 극이 같을 경우
   c. A와 B 모두 회전 X → 애초에, A가 회전하지 않는 경우
   

톱니바퀴 초기 상태, 회전시키는 톱니바퀴 번호, 회전 방향이 주어지면 최종 상태를 리턴하는 함수를 만들어라.

예시

위 그림에서 최초로 3번을 반시계 방향으로 회전했다면, 4번은 시계 방향으로 회전하게 된다. 2번은 3번과 맞닿은 부분이 같기 때문에, 회전하지 않게 되고, 1번은 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위 상태에서 최초로 1번을 시계 방향으로 회전시키면, 2번이 반시계 방향, 3번은 시계 방향으로 회전하게 된다. 4번은 3번과 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

입력

• 1 ~ 4번째줄 : 톱니바퀴 상태 (0 = N극, 1 = S극)
• 5번째 줄 : 회전 횟수 (K)
• 6번째 줄 ~ 마지막 줄 : 회전시킨 톱니바퀴 번호, 회전 방향

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

내 풀이

현재 톱니바퀴(B)가 회전할 수 있는지 알기 위해선, 이전 톱니바퀴(A)와 함께 다음 2가지 조건을 따져봐야한다.

1. A가 회전 했는가?
   O : B는 2번 조건을 만족하면 회전할 수 있다.
   X : B는 애초에 회전할 수 없다.
2. A와 B가 맞닿은 톱니의 극이 다른가?
   O : B는 회전할 수 있다.
   X : B는 회전할 수 없다.

재귀 함수

이 조건들을 쉬운 방법으로 확인하기 위해 재귀 함수를 사용하여 마지막으로 회전하는 톱니바퀴부터 시작해서 처음에 회전시킨 톱니바퀴의 순으로 톱니바퀴를 회전키는 연산을 하였다.

재귀 함수는 다음과 같은 인자를 받는다.

cur

현재 연산하는 톱니바퀴 인덱스다. 재귀를 돌릴 때마다 양쪽으로 +1, -1 해주어 모든 톱니바퀴에 대해 함수를 실행시킨다.

dir

톱니바퀴를 회전 시킬 방향이다. 각 톱니바퀴마다 회전 방향(1, -1)이 다르므로 -를 붙여 방향을 바꿔서 함수를 실행시킨다.

visit

각 톱니바퀴에 대한 함수 실행 여부를 기록해 놓은 배열이다. 각 함수를 실행시킬 때마다, 인덱스에 기록하여 무한루프가 돌지 않게끔 한다.

canRotate

이전 톱니바퀴의 회전 여부다. 현재 톱니바퀴와 이전 톱니바퀴 둘 다 회전이 가능해야 현재 톱니바퀴는 회전할 수 있다. 이 값을 다음 함수의 canRotate로 넘겨주어 계속 비교해준다.

회전 함수

현재 톱니바퀴의 회전 방향(시계 = 1, 반시계 = -1)을 보고 다음과 같이 톱니를 재배치한다.

시계 방향

마지막 톱니를 빼내어(pop()), 첫번째 톱니 앞에 넣는다. (unshift())

반시계 방향

첫번째 톱니를 빼내어(shift()), 마지막 톱니 뒤에 넣는다. (push())

전체 코드

const fs = require("fs");
const path = require("path");
const filepath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const splitStr = process.platform !== "win32" ? "\n" : "\r\n";
const input = fs
  .readFileSync(path.resolve(__dirname, filepath))
  .toString()
  .trim()
  .split(splitStr);

const wheels = input.slice(0, 4).map((e) => e.split("").map(Number));
const n = +input[4];
const moves = input.slice(5, 5 + n + 1).map((e) => e.split(" ").map(Number));

function solution(wheels, moves) {
  // 각 move마다 재귀 돌려서 톱니바퀴 업데이트
  moves.forEach(([num, dir]) => {
    const visit = Array(4).fill(0);
    rec(num - 1, dir, visit, true);
  });

  let score = 0;

  // 점수 구하기
  wheels.forEach(([w, ..._], num) => {
    if (w === 1) {
      if (num === 0) score += 1;
      if (num === 1) score += 2;
      if (num === 2) score += 4;
      if (num === 3) score += 8;
    }
  });

  return score;

  // 재귀 함수
  function rec(cur, dir, visit, canRotate) {
    // 현재 톱니바퀴 방문처리
    visit[cur] = 1;

    const prev = cur - 1;
    const next = cur + 1;

    // 전번 톱니바퀴
    if (prev >= 0 && !visit[prev]) {
      // 이전 톱니바퀴가 돌지 않으면 현재 톱니바퀴도 돌지 못함
      rec(prev, -dir, visit, wheels[cur][6] !== wheels[prev][2] && canRotate);
    }

    // 후번 톱니바퀴
    if (next <= 3 && !visit[next]) {
      // 이전 톱니바퀴가 돌지 않으면 현재 톱니바퀴도 돌지 못함
      rec(next, -dir, visit, wheels[cur][2] !== wheels[next][6] && canRotate);
    }

    // 현재 톱니바퀴 돌림
    if (canRotate) {
      if (dir === 1) wheels[cur].unshift(wheels[cur].pop());
      if (dir === -1) wheels[cur].push(wheels[cur].shift());
    }
  }
}

console.log(solution(wheels, moves));

Link

• https://www.acmicpc.net/problem/14891