알고리즘문제 5

너무어려워이거....완젼히 다 맞지는못했다...

 

function minimumTreePath(n, edges, visitNodes) {
    const INF = 1e9;
    const dist = Array(n).fill().map(()=> Array(n).fill(INF));
    const visit = visitNodes.map(v => v-1);
    
    edges.forEach(([u, v]) =>{
    dist[u-1][v-1] =1;
    dist[v-1][u-1] =1;
    });
    
    for(let k=0; k < n; k++)
    for(let i=0; i <n; i++)
    for (let j=0; j<n; j++)
    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    
    let minPath = INF;
    for(let perm of permutations(visit)){
        let prev =0, len =0;
        for (let node of perm){
            len += dist[prev][node];
            prev = node;
        }
        len += dist[prev][n-1];
        minPath = Math.min(minPath, len);
    }
    return minPath;
}

function* permutations(array, n = array.length){
    if(n === 1) yield array.slice();
    else{
        for(let i = 0; i <n; i++){
            yield* permutations(array, n-1);
            [array[n%2 ? 0 : i], array[n-1]] = [array[n-1], array[n%2 ? 0 : i]];
        }
    }
}