백준 13913번: 숨바꼭질4 (javascript, BFS)

숨바꼭질 문제의 변형판이다. 최단경로와 그 경로를 출력해야 한다. 최단경로는 이전에 구한 것처럼 BFS를 이용해 구할 수 있다. 

새로운 배열을 선언하고 방문한 점의 위치에 이전 점의 위치를 저장하고, 목표 위치인 K에 도착했을 때 반복문으로 이전 좌표들을 따라감으로써 방문경로를 확인하였다.

 

코드는 다음과 같다.

const fs = require('fs');
let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a))

function BFS(x, k){
    let queue = [x]
    let array = new Array(MAX).fill(0)
    let path = new Array(MAX).fill(0)
    if(x === k){
        return [0, x]
    }
    else{
        while(queue.length){
            let y = queue.shift()
            if(y === k){
                const min = array[y]
                let backtrack = String(k)
                let start = y
                while(start !== x){
                    backtrack = String(path[start]) + ' '+backtrack
                    start = path[start]
                }
                return [min, backtrack]
            }
            for(const move of [y-1, y+1, 2*y]){
                if(move <= 100001 && !array[move]){
                    queue.push(move)
                    // 걸리는 시간 체크
                    array[move] = array[y]+1
                    path[move] = y
                }
            }
        }
    }
}

const MAX = 100001
const [min, track] = BFS(N, K)
console.log(min)
console.log(track)