[JS] 백준 - 13549(숨바꼭질 3)

처음 풀이

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

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [start, end] = input()
  .trim()
  .split(" ")
  .map((v) => Number(v));

const graph = Array(100001).fill(0);
const visited = Array(100001).fill(false);
visited[start] = true;

console.log(bfs([start]));

function bfs(q) {
  if (start === end) return 0;
  while (q.length) {
    const limit = q.length;

    for (let i = 0; i < limit; i++) {
      const curr = q.shift();
      const next = [curr * 2, curr + 1, curr - 1];
      for (let k = 0; k < 3; k++) {
        if (next[k] >= 0 && next[k] < 100001) {
          if (!visited[next[k]]) {
            visited[next[k]] = true;
            if (k === 0) {
              graph[next[k]] = graph[curr];
            } else {
              graph[next[k]] = graph[curr] + 1;
						}
						q.push(next[k]);
          } else {
            if (k === 0) {
              graph[next[k]] = Math.min(graph[curr], graph[next[k]]);
            } else {
              graph[next[k]] = Math.min(graph[curr] + 1, graph[next[k]]);
            }
          }
        }
      }
    }
	}
	return graph[end]
}

2가지 경우로 나누어서 생각했었습니다. 순간이동을 할 경우 시간이 증가하지 않기 때문에 예외 처리를 해줘야 했습니다.

문제를 푸는 아이디어

• 처음 방문을 한 경우와 한번 이상 방문한 경우를 나누었습니다.
• 처음 방문했을 경우 (visited[idx]가 false인 경우) 순간 이동은 시간 그대로 넣어줬습니다. 아닐 경우 시간 +1
• 두번 째 방문했을 경우, 최소의 시간을 구하기 위해 입력 되어 있는 시간과 비교하는 시간 중에 최소 값을 넣어줬습니다.

이렇게 전부 값을 비교해주고 최종적으로 목적지의 index의 최소 값을 return 해줬습니다.

하지만 중복되는 코드가 길고 복잡하여 간단하게 해결할 수 있는 코드를 찾았습니다.

다른 풀이

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

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [start, end] = input()
  .trim()
  .split(" ")
  .map((v) => Number(v));
const visited = Array(100001).fill(false);

const queue = [[start, 0]];
console.log(bfs(queue));

function bfs(que) {
  while (que.length) {
    const [curr, idx] = que.shift();
    visited[curr] = true;
    if (curr === end) return idx;

    for (const next of [curr * 2, curr + 1, curr - 1]) {
      if (next >= 0 && next < 100001 && !visited[next]) {
        if (next === curr * 2) que.unshift([next, idx]);
        else que.push([next, idx + 1]);
      }
    }
  }
}

unshift를 사용하여 우선순위를 높여주는 방법입니다. 순간 이동했을 때는 시간이 증가하지 않기 때문에 순간이동을 많이하면 할수록 유리합니다. 그래서 순간이동을 한 경우만 unshift를 사용하여 que 맨 앞으로 보내서 처음으로 계산해줍니다.