[G4] 숨바꼭질4

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

DFS로 탐색하는 경우, TLE가 발생한다.

DFS의 경우, 함수가 실행된 이상 모든 노드를 방문하고, BFS는 조건을 만족하는 경우 실행을 멈춘다.

 

특정 원소, 노드를 방문했을 때, 방문 유무를 기록하는 방법에는 Set을 이용하는 방법도 있고, 배열을 이용하는 방법도 있다. 아무래도 배열의 인덱스로 접근하는 방식이 속도 면에서는 좀 더 괜찮을 듯?

 

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ').map(el => +el);

solution(input);

function solution(data) {
    const visited = Array.from({ length: 100001 }, () => 0);
    const path = Array.from({ length: 100001 }, () => 0);
    const [posN, posK] = data;
    
    const minTime = findMinTime();
    console.log(`${minTime}\n${findMinPath(minTime)}`);
    
    function findMinPath(time) {
        const visitOrder = [posK];
        let prev = path[posK];
        
        for(let i = 0; i < time; i++) {
            visitOrder.push(prev);
            prev = path[prev];
        }
        const result = `${visitOrder.reverse().join(' ')}`;
        return result
    }

    function findMinTime() {
        const q = [[posN, 0]];
        visited[posN] = 1;

        while (q.length !== 0) {
            let [curPos, time] = q.shift();
    
            if (curPos === posK) {
                return time;
            }
            for(let next of [curPos - 1, curPos + 1, curPos * 2]) {
                if(next > 100000 || next < 0 || visited[next]) continue;
                visited[next] = 1; 
                path[next] = curPos;
                q.push([next, time + 1]); 
            }
        }
    }
}