백준 2178번 - 숨바꼭질 (Silver1, JS, DFSBFS)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map((v) => +v);
let map = new Array(100001).fill(0);
function solution(n, k) {
let queue = [[n, 0]];
map[n] = 1;
while (queue.length > 0) {
const [x, count] = queue.shift();
if ( x === k ) { console.log(count); break;}
for (let nx of [x - 1, x + 1, x * 2]) {
if (nx >= 0 && nx <= 100000 && map[nx] === 0) {
map[nx] = 1;
queue.push([nx, count + 1]);
}
}
}
}
solution(N, K);
처음에 작성했던 코드에서는 시간 초과가 떴다.
map배열을 만들어 이미 갔던 지점은 가지 않도록 해 중복방지해 시간단축을 했다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map((v) => +v);
let map = new Array(100001).fill(0);
function solution(n, k) {
let queue = [n];
map[n] = 1;
while (queue.length > 0) {
const len = queue.length;
for (let i = 0; i < len; i++) {
const x = queue.shift();
if ( x === k ) { console.log(count); break;}
for (let nx of [x - 1, x + 1, x * 2]) {
if (nx >= 0 && nx <= 100000 && map[nx] === 0) {
map[nx] = 1;
queue.push(nx);
}
}
}
count++;
}
}
solution(N,K);
그런 다음,
queue를 2차원 배열이여서 좀 더 빠르게 처리하기 위해 1차원 배열로 수정하였다.
const [N, K] = require("fs").readFileSync("/dev/stdin").toString().trim().split(' ').map(Number);
const map = new Array(100001).fill(0);
if (N === K) {
console.log(0);
} else {
BFS();
console.log(map[K] - 1);
}
function BFS() {
const queue = [N];
let idx = 0;
map[N] = 1;
while (true) {
const x = queue[idx];
const dx = [x * 2, x + 1, x - 1];
idx++;
for (let i = 0; i < 3; i++) {
const nx = dx[i];
if (nx >= 0 && nx < 100001 && map[nx] === 0) {
map[nx] = map[x] + 1;
queue.push(nx);
if (nx === K) {
return;
}
}
}
}
}
3중 반복문이 아니라 2중 반복문으로 해결할 수 없을까 하다가 찾은 어느 분의 솔루션!
shift()로 첫 번째 요소를 제거하지 않고, 대신 인덱스로 접근해서 값을 꺼내온다!! 그러면 count는 어떻게 해야할까? (3중 for문의 사용이유: count )
map에 1,0 으로 방문 여부만 판단하지 않고, count를 입력한다.