-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
이거 크루스칼로 풀어도 풀리는데 맞는건가요?
23.04.06 23:05 작성 조회수 231
0
const p = [
[1, 2, 6],
[1, 3, 3],
[3, 2, 2],
[2, 4, 1],
[2, 5, 13],
[3, 4, 5],
[4, 2, 3],
[4, 5, 7],
];
solution(p, 5, 8);
function solution(p, city, line) {
p.sort((a, b) => a[2] - b[2]);
const unf = Array(city + 1).fill(0);
for (let i = 0; i < city + 1; ++i) unf[i] = i;
function find(v) {
if (v === unf[v]) return v;
else return (unf[v] = find(unf[v]));
}
function union(f1, f2) {
const c1 = find(f1);
const c2 = find(f2);
if (c1 != c2) {
unf[c1] = c2;
return true;
}
return false;
}
let cost = 0;
for (let i = 0; i < p.length; ++i) {
const [c1, c2, val] = p[i];
if (union(c1, c2)) {
cost += val;
}
}
return cost;
}
크루스칼로 풀어도 풀리는데
이것도 맞는 풀이인가요?
테스트 케이스가 더 잇엇으면 좋겟네요
답변을 작성해보세요.
1
김태원
지식공유자2023.04.07
안녕하세요^^
문제가 모든 정점에서 모든 정점으로 가는 최소비용을 각각 2차원 배열에 구하라는 의미입니다. 영상처럼 2차원 배열 dist에 각각 최소비용를 구해야 합니다. dist[i][j] 값의 의미는 i번 정점에서 j번 정점으로 가는 최소비용입니다. 답을 2차원 배열로 구하는 플로이드 워샬 차제를 많이 연습하세요. 플로이드 워샬을 통해 구한 2차원 최소비용 배열을 이용해 문제를 해결하는 응용문제가 요즘 많이 나옵니다.
답변 1