[baekjoon] 12869 뮤탈리스크 (Javascript)

12869번: 뮤탈리스크 (acmicpc.net)

12869번: 뮤탈리스크

---

알고리즘 : bfs / dp?

 

최소값 => bfs를 생각해서 bfs로 풀었다.

풀고나서 찾아보니 dp로도 많이 푸는 것 같긴한데 흠... 아직 잘 모르겠다.

 

경우의 수만큼 시도하면서 Layer를 파악하는 것이 핵심!

익숙하지 않아서 어려웠던 문제!

 

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());
let n = +input.shift();
let scv = input
  .shift()
  .split(" ")
  .map((v) => +v);

let arr = [
  [9, 3, 1],
  [9, 1, 3],
  [3, 9, 1],
  [3, 1, 9],
  [1, 3, 9],
  [1, 9, 3],
];

let vis = Array.from({ length: 61 }).map((_) => new Array(61).fill(0).map((__) => new Array(61).fill(0)));
const bfs = (start) => {
  let queue = [];
  vis[start[0]][start[1]][start[2]] = 1;
  queue.push(start);
  while (queue.length) {
    let [c1, c2, c3] = queue.shift();
    for (let i = 0; i < arr.length; i++) {
      let n1 = Math.max(0, c1 - arr[i][0]);
      let n2 = Math.max(0, c2 - arr[i][1]);
      let n3 = Math.max(0, c3 - arr[i][2]);

      if (vis[0][0][0]) break;
      if (vis[n1][n2][n3]) continue;
      vis[n1][n2][n3] = vis[c1][c2][c3] + 1;
      queue.push([n1, n2, n3]);
    }
  }
  return vis[0][0][0] - 1;
};

function solution() {
  let ans = 0;
  for (let i = 0; i < 3; i++) {
    if (!scv[i]) scv[i] = 0;
  }

  ans = bfs(scv);

  console.log(ans);
}

solution();