• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

이거 크루스칼로 풀어도 풀리는데 맞는건가요?

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

답변을 작성해보세요.

1

안녕하세요^^

문제가 모든 정점에서 모든 정점으로 가는 최소비용을 각각 2차원 배열에 구하라는 의미입니다. 영상처럼 2차원 배열 dist에 각각 최소비용를 구해야 합니다. dist[i][j] 값의 의미는 i번 정점에서 j번 정점으로 가는 최소비용입니다. 답을 2차원 배열로 구하는 플로이드 워샬 차제를 많이 연습하세요. 플로이드 워샬을 통해 구한 2차원 최소비용 배열을 이용해 문제를 해결하는 응용문제가 요즘 많이 나옵니다.