接続[python]貪欲法島(3段階)

問題の説明

n個の島の間に橋を建設する費用(費用)については、すべての島が最小の費用で互いに通行できるようにする解決策を完了し、必要な最小の費用を返してください.
橋を何度も渡っても、たどり着けば通行できます.例えば、A島とB島の間に橋があり、B島とC島の間に橋があれば、A島とC島は互いに通行することができる.

せいげんじょうけん

島の個数nは1以上100以下である.
コストの長さは(n−1)*n)/2以下である.
任意のiについて、cost[i][0]とcost[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

I/O例説明

コストは次の図のようになります.
緑のパス接続を使用することは、最小限のコストですべての人が通行できる方法です.

問題を解く

# n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때,
# 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때
# 필요한 최소 비용을 return하시오.
# costs의 길이 : i <= ((n-1) * n) / 2 -> 순서가 바뀌더라도 같은 연결로 봅니다

def solution(n, costs):
    answer = 0
    i = 0
    j = 0
    
    for i in range(costs):
    	if i <= ((n-1) * n) / 2:
            for cost[i][j+2] in range(costs):
               
    return answer

Kruskalアルゴリズムを用いると簡単に解くことができる.
Kruskalアルゴリズムとは?
貪欲法を用いてネットワークの頂点を最小限のコストで接続する.
ここで、貪欲な方法は、タイムリーに最高の選択をして、最高の結果を達成することです.
Kruskalアルゴリズムでは,コアはループを生成しない.
ループの生成を避けるために、追加する幹線の両端点は同じ集合に属しません.
そのため、Union-Findアルゴリズムがあります.

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2]) 
    link = set([costs[0][0]])

    # Kruskal 알고리즘으로 최소 비용 구하기
    while len(link) != n:
        for v in costs:
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
                link.update([v[0], v[1]])
                answer += v[2]
                break
                
    return answer

問題の説明の作成

step 1

	costs.sort(key = lambda x: x[2]) 
    link = set([costs[0][0]])

costs.sort(key = lambda x: x[2]) before : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] after : [[0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]]<lamdaソート>costs.sort(key = lambda x: x[2])

keyは、2次元アレイ内部の特定の値に基づいて

をキャプチャするために使用することができる.

x[2]:原価順
❔:並べ替えの原因|𐥎8|

まずコストが最も低い条件を計算

以下の設定を使用

link = set([costs[0][0]])setリスト

に開始接続点を追加

step 2

    while len(link) != n:
        for v in costs:
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
                link.update([v[0], v[1]])
                answer += v[2]
                break

while len(link) != n:

setで接続されたすべての位置が接続前に実行される条件

問題の制限:島の接続が許可されていないことを満たす

if v[0] in link and v[1] in link:

2つの島がより低い価格で接続されている場合は無視

if v[0] in link or v[1] in link:

2つの島の1つが接続されていない場合、コストは増加します

link.update([v[0], v[1]])

set.update()重複除外

島が接続されている場合は、他の島を追加せずにn個の冗長島を保持することができる