220218-接続島

接続◾島：プログラマーLEVEL 3

https://programmers.co.kr/learn/courses/30/lessons/42861

質問する

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例

ncostsreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4

のり付け

1.解説

クルーズアルゴリズムを用いて島を接続する最小費用を求めた.

建設の場合、料金の低い幹線を先に接続します.

段で、ループが発生した場合は、この幹線は使用されません.

を選択した幹線が(島の個数-1)であれば、すべての島が接続されます.

2.プログラム

幹線建設費用順(降順)

最低コスト幹線から順に追加し、

を確定する.

リングがある場合は、

は追加されません.

幹線プラス料金返還

# 코드
def find(p, u):
    if u != p[u]:
        p[u] = find(p, p[u])
    return p[u]

def union(p, u, v):
    root1 = find(p, u)
    root2 = find(p, v)
    p[root2] = root1

def solution(n, costs):
    answer = 0
    p = [i for i in range(n+1)]
    costs.sort(key=lambda x : x[2], reverse=True)

    edges_cnt = 0
    while True:
        if edges_cnt == n-1:
            break
        u, v, cost = costs.pop()
        if u > v :
            u, v = v, u
        if find(p, u) != find(p, v):
            union(p, u, v)
            answer += cost
            edges_cnt += 1

    return answer