プログラマー-島接続

島接続（2021、07.30）Connect Island

質問と回答アドレス

Programmers
Git Solution

問題の説明

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
I/O例説明
コストは下図のように、緑のパス接続を使用すると、すべての人が通過できるように最小限のコストで使用できます.

トラブルシューティング

この問題はテーマ貪欲法を含め,多様なアルゴリズムが必要である.(またシャベルを1本投げた…)必要なアルゴリズムは次のとおりです.
クルーズアルゴリズム

パターン内のすべての頂点を含み、ループのない接続線を描画する場合、重み付けと最小を求める場合は

を使用します.

最小伸長木を求めるアルゴリズム

実際のクルーズアルゴリズムは、配列の初期値をノードの値とし、ノードを表示および実装しないため、初期値を-1

として指定する
クルーズアルゴリズムの実現方式

配列の開始値と終了値のナビゲーション(DFS)を使用して、最終的な親値を検索します.

で求めた開始値の親値と終了値の親値を比較します.

比較値の大きい値がアクセス配列のインデックス値となり、小さい値がそのアクセス配列の値となる.

の開始値の親値が終了値の親値と同じである場合、사이클は作成すべきでない形になります(A->B<->C).したがって、動作は発生しません.

推測イベントと解決策

初期には、私はクルーズアルゴリズムを使わず、定義した条件を絶えず追加することで解いた.△間違ったやり方とは言えないが、条件はますます厳しくなっている.ループを作成しない方法を開始値と終了値の2つに分けて処理し、コンテキストループを作成するために条件値を追加しました.多くのテストケースが追加され、実際のテストケースで条件が作成されましたが、いずれも失敗します.条件ごとに状況によって異なるので,この方式は不可能であることに気づく.

≪イベント｜Events｜ldap≫

トラブルシューティング

クルースカアルゴリズムを用いた.
最上位の親ノードを検索するコードは次のとおりです.

// 재귀함수를 사용하여 -1값이 나올때까지
private int findRoot(int child, int[] visitArr) {
    if(child == visitArr[child]){
        return child;
    }else if (visitArr[child] == -1) {
        return child; // 기존 부모값 사용
    } else {
        return findRoot(visitArr[child], visitArr);
    }
}

アクセス配列に値を設定する条件は次のとおりです.

// 순서가 상관없으므로 두 root값을 모두 비교해야한다.
// 큰값이 방문배열 Index, 작은값이 방문배열 Value
if(startRoot > endRoot){
    visitArr[startRoot] = endRoot;
}else{
    visitArr[endRoot] = startRoot;
}
// 양쪽 부모가 같지 않으므로 연결이 가능하므로 연산한다.
answer += cost[2];

テスト結果

試験番号通過有無メモリと時間試験番号通過有無メモリと時間試験番号通過(11.49 ms,53.5 MB)試験5通過(6.98 ms,52.8 MB)試験2通過(4.35 ms,52.3 MB)試験6通過(6.56 ms,52.4 MB)試験3通過(4.39 ms,53.3 MB)試験7通過(12.55 ms,52.1 MB)試験4通過(9.10 ms,53.3 MB)試験8通過(6.82 ms,52.1 MB)

ポスト

この問題は明確なアルゴリズム(クルスカ)を用いず,条件を設定すれば解決できる.相応の条件を考慮したが,依然として脆弱性があり,所望の結果は得られなかった.