[Gold 4]1922号:ネットワーク接続
🛠 質問する
https://www.acmicpc.net/problem/1922
👩🏻💻 解決策
これは典型的な最小費用タイプの問題であり,単独で適用する必要はなく,クルーズアルゴリズムを用いてのみ解くことができる.
ただ効率が悪いので、次の問題を解くときは効率を考えなければなりません.
ソースコード
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n = int(input())
m = int(input())
parent = [0] * (n + 1)
for i in range(1, n+1):
parent[i] = i
edges = []
result = 0
for i in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
💡 他人の解答
n = int(input())
m = int(input())
costs = [list(map(int, input().split())) for _ in range(m)]
# 비용을 기준으로 오름차순 정렬
costs.sort(key=lambda x: x[2])
# set 자료구조 이용
s = {costs[0][0]}
# 정답
answer = 0
# set에 모든 컴퓨터가 들어오기전까지 돌리기
while len(s) != n:
for idx, cost in enumerate(costs):
# 양쪽 node가 이미 자료구조에 들어있다면 무시
if cost[0] in s and cost[1] in s:
continue
# 둘중 하나의 노드만 들어가있을 경우
if cost[0] in s or cost[1] in s:
# 비용 추가
answer += cost[2]
# set자료구조에 update반영
s.update([cost[0], cost[1]])
# 한번 훑고 나온 노드 연결 정보는 -1로 바꾸어줘서 다음번에 영향을 미치지 않는다
costs[idx] = [-1, -1, -1]
# 최소비용을 담았으면 탈출하고 다시 처음부터 훑어서 방금 연결된 노드와 연결된 노드를 계속 찾는다
break
print(answer)
Reference
この問題について([Gold 4]1922号:ネットワーク接続), 我々は、より多くの情報をここで見つけました https://velog.io/@hyunnn/골드4-1922번-네트워크-연결テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol