[7211] Ringsõit

https://www.acmicpc.net/problem/7211

 

유니온 파인드의 기본 문제다.

---

풀이 방법

입력되는 간선 정보를 저장한다.

이때 국가소유의 간선인지 아닌지 또한 저장해야 한다.

 

간선정보를 비용순서로 정렬. 모든 단선을 탐색하며 유니온 과정을 수행한다.

• 해당 간선이 국가소유의 간선이며 최소 스패닝 트리에 포함되어야 하는 간선이라면 비용을 0으로 하여 필요한 비용으로 추가한다.
• 해당 간선이 국가소유의 간선이지만 최소 스패닝 트리에 포함하면 안 되는 간선이라면 해당 간선의 비용을 필요한 비용에서 빼준다.
• 국가소유의 간선이 아니라면, 최소 스패닝 트리에 포함되는지 여부를 확인한 뒤 필요한 비용에 반영하면 된다.

필요한 비용이 0보다 작다면 0을 출력. 그 이상이라면 해당 비용을 출력하면 된다.

---

정답 코드

	import Foundation
	let (N,M,K) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
	var ans = 0
	var comp = N
	var arr = Array(repeating: -1, count: N)
	var edges = [(u:Int, v:Int, cost:Int, nation:Bool)]()
	func root(of node:Int) -> Int{
	if arr[node]<0 { return node }
	arr[node] = root(of: arr[node])
	return arr[node]
	}
	func union(a:Int, b:Int, cost:Int, nation:Bool){
	let ra = root(of: a)
	let rb = root(of: b)
	if ra == rb {
	ans -= nation ? cost:0
	return
	}
	arr[rb] = ra
	comp -= 1
	ans += nation ? 0:cost
	}
	for _ in 0..<M{
	let (u,v,c) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0]-1, $0[1]-1, $0[2])}[0]
	edges.append((u,v,c,true))
	}
	for _ in 0..<K{
	let (u,v,c) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0]-1, $0[1]-1, $0[2])}[0]
	edges.append((u,v,c,false))
	}
	edges.sort(by: {$0.cost > $1.cost})
	while !edges.isEmpty{
	let edge = edges.removeLast()
	union(a: edge.u, b: edge.v, cost: edge.cost, nation: edge.nation)
	}
	print(ans<0 ? 0:ans)

view raw 7211.swift hosted with ❤ by GitHub