[백준] 13913 숨바꼭질4 - javascript
📌 문제
https://www.acmicpc.net/problem/13913
📌 풀이
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, k] = input[0].split(" ").map(Number);
let visited = new Array(100001).fill(0);
let path = new Array(100001).fill(0);
function BFS() {
let L = 0;
let queue = [];
queue.push(n);
visited[n] = 1;
while (queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let x = queue.shift();
if (x === k) {
return L;
}
for (let nx of [x + 1, x - 1, x * 2]) {
if (visited[nx] === 0 && nx >= 0 && nx <= 100000) {
path[nx] = x;
visited[nx] = 1;
queue.push(nx);
}
}
}
L++;
}
}
let time = BFS();
let ans = [];
let before = path[k];
ans.push(k);
for (let i = 0; i < time; i++) {
ans.push(before);
before = path[before];
}
console.log(`${time}\n${ans.reverse().join(" ")}`);
✔ 알고리즘 : BFS
✔ 기존의 숨바꼭질 문제에서 경로만 추가하여 출력해주면 되는 문제이다.
✔ 경로를 추적하기 위해 path 배열을 생성하였고 x위치에서 파생되는 nx로 이동가능 하다면 path[nx]에 x를 넣어주어 경로역추적이 가능하게끔 구현하였다.
✔ BFS 함수의 return 값으로 동생을 찾는 가장 빠른 시간을 저장한다.
✔ ans배열에 가장 빠른 시간으로 갈 수 있는경로를 저장하였다.
✔ 동생이 있는 지점부터 path배열을 통해 직전에서 어디서 왔는지 ans배열에 저장해준다
✔ 역추적한 경로이므로 reverse함수를 사용하여 뒤집은 후 join으로 띄어쓰기하여 출력해주었다
✔ 난이도 : 백준 기준 골드4
Author And Source
이 문제에 관하여([백준] 13913 숨바꼭질4 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-13913-숨바꼭질4-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)