백준 2178번 - 숨바꼭질 (Silver1, JS, DFSBFS)

백준 2178번 - 숨바꼭질 (Silver1, JS, DFSBFS)

1. 문제설명

2. 입출력 예 & 제한사항

3. Solution

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를 입력한다.