接続プログラマー-島

7735 ワード
プログラマ アルゴリズム#アルゴリズム# コーディングテスト テキストリンク

1.質問


質問リンク
説明:
n個の島の間に橋を建設する費用(費用)については、すべての島が最小の費用で互いに通行できるようにする解決策を完了し、必要な最小の費用を返してください.
橋を何度も渡っても、たどり着けば通行できます.例えば、A島とB島の間に橋があり、B島とC島の間に橋があれば、A島とC島は互いに通行することができる.
せいげんじょうけん
  • 島の個数nは1以上100以下である.
  • コストの長さは(n−1)*n)/2以下である.
  • の任意iについては、コスト[i][0]とコスト[i][1]は、橋を結ぶ2つの島の番号を含み、コスト[i][2]は、この2つの島を結ぶ橋を建設するのに必要な費用である.
  • のような接続は2回も提供されません.また、順序が変更されると、同じ接続とみなされます.つまり、0と1の間に接続が確立されている場合、1と0は必要ありません.
  • すべての島間の橋梁建設費用は支払われません.この場合,二つの島の間に建設することは不可能であると考えられる.
  • に接続できない島を与えない.
    • I/O例
    numberscostreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4
    I/O例説明
    コストは下図のように、緑のパス接続を使用すると、すべての人が通過できるように最小限のコストで使用できます.

    2.解答


    典型的なMST問題.
    私はクルーズアルゴリズムで問題を解決します.

    3.完全なコード

    function solution(n, costs) {
    // 크루스칼 알고리즘 구현에 필요한 유니온 파인드 함수들과 변수 선언
    const set = [...Array(n)].map((_, i) => i);

    const find = a => set[a] = a == set[a] ? a : find(set[a]);

    const union = (a, b) => {
        a = find(a);
        b = find(b);

        a > b ? set[a] = b : set[b] = a;
    };

    const is_same_parent = (a, b) => find(a) == find(b);

    return (
        costs
            .sort((a, b) => a[2] - b[2])
            .reduce((m, [a, b, cost]) => {
                // a와 b가 연결됐다면 넘어가기
                if (is_same_parent(a, b)) return m;
                
                // a, b를 연결
                union(a, b);
                
                // 비용 누적
                m += cost;
                return m;
            }, 0)
    );
}
    Vscodeは私の環境を解決するのに時間がかかると愚痴をこぼしています.
    eetcode - 3sum closest(kotlin)