[백준/G5] 14891 톱니바퀴

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

시간복잡도

O(N**2)

풀이

방문과정과 회전과정을 분리하여 풀이함

방문 과정은 dfs와 visited를 활용하여 방문(회전할수 있는지)한적 있는지 체크하며 회전시킴

회전과정은 인덱싱과 나머지를 사용해서 두가지 방향으로 조절

function rotate(gear, direction) {
  let rotatedGear = Array(8).fill(0);

  if (direction === 1) {
    // 시계방향 회전
    for (let i = 0; i < 8; i++) {
      rotatedGear[(i + 1) % 8] = gear[i];
    }
  } else {
    // 반시계방향 회전
    for (let i = 0; i < 8; i++) {
      rotatedGear[i] = gear[(i + 1) % 8];
    }
  }
  return rotatedGear;
}

function moveGear(gears, num, direction, visited) {
  // 방문한적 있다면 return
  if (visited[num]) return;
  // 방문체크
  visited[num] = true;

  // 왼쪽
  if (num > 0 && gears[num][6] !== gears[num - 1][2]) {
    moveGear(gears, num - 1, -direction, visited);
  }
  // 오른쪽
  if (num < 3 && gears[num][2] !== gears[num + 1][6]) {
    moveGear(gears, num + 1, -direction, visited);
  }

  // 업데이트(회전)
  gears[num] = rotate(gears[num], direction);
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./14891.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const arr = input.slice(0, 4).map((l) => l.trim().split("").map(Number));
const K = parseInt(input[4]);
const orders = input
  .slice(5, 5 + K)
  .map((o) => o.trim().split(" ").map(Number));

let temp = arr.map((row) => [...row]);

// 순서대로 톱니바퀴 회전
orders.forEach((order) => {
  let visited = Array(4).fill(false);
  const [num, direction] = order;
  moveGear(temp, num - 1, direction, visited);
});

// 계산
let ans = temp.reduce((acc, val, idx) => acc + val[0] * Math.pow(2, idx), 0);
console.log(ans);

9416kb 104ms

속도는 dfs로 푸는게 괜찮은 선택이었던 것 같긴한데, 다시보니 꼭 dfs로 풀어야하는 문제는 아니었다