-
알고리즘문제 5헬리'Daily/꾸준한 알고리즘 2023. 5. 29. 01:38728x90
너무어려워이거....완젼히 다 맞지는못했다...
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]]; } } }
728x90'헬리'Daily > 꾸준한 알고리즘' 카테고리의 다른 글
[프로그래머스] 코테 (k의 개수) (0) 2023.07.27 [프로그래머스] 코테 (팩토리얼) (0) 2023.07.22 알고리즘문제 4 (0) 2023.05.29 알고리즘문제 3 (0) 2023.05.29 알고리즘 문제 2 (0) 2023.05.29