알고리즘 : bfs
bfs는 2차원에 익숙해서 그외의 경우가 더어렵다고 느껴진다.
이번 문제는 max값을 설정하지 않아서 고생했다.
로직은 맞는데 자꾸 틀려서 max값을 문제의 최대값 *2로 변경했더니 풀린다!
예외처리에 집중하자!!
function solution() {
let input = require("fs")
.readFileSync("input.txt") //"/dev/stdin"
.toString()
.split("\n")
.map((val) => val.trim());
let [n, k] = input
.shift()
.split(" ")
.map((v) => +v);
let max = 200000;
// 1초후 x-1 or x+1
// 1초후 2*x
let ans = new Array(max + 4).fill(0);
let vis = new Array(max + 4).fill(0);
// 모든 경우의 수를 확인? ->2초 가능할듯
const check = (start, end) => {
let queue = [];
vis[start] = 1;
ans[start] = 1;
queue.push(start);
while (queue.length) {
let cx = queue.shift();
for (let dir = 0; dir < 3; dir++) {
let nx;
if (dir === 0) nx = cx * 2;
else if (dir === 1) nx = cx + 1;
else nx = cx - 1;
if (nx >= 0 && nx < max) {
if (!vis[nx]) {
queue.push(nx);
vis[nx] = vis[cx] + 1;
ans[nx] += ans[cx];
} else if (vis[nx] === vis[cx] + 1) {
ans[nx] += ans[cx];
}
}
}
}
};
check(n, k);
console.log(vis[k] - 1);
console.log(ans[k]);
}
solution();
'코딩테스트(알고리즘) > baekjoon' 카테고리의 다른 글
[baekjoon] 13023 ABCDE (Javascript, Python) (0) | 2023.02.27 |
---|---|
[baekjoon] 16953 A->B (Javascript, Python) (0) | 2023.02.27 |
[baekjoon] 16637 괄호 추가하기 (Javascript) (1) | 2023.02.02 |
[baekjoon] 12869 뮤탈리스크 (Javascript) (0) | 2023.02.01 |
[baekjoon] 16234 인구 이동 (Javascript) (0) | 2023.01.31 |