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

 

23743번: 방탈출

첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으

www.acmicpc.net

기본적인 MST 문제다. 

 

풀이

두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다. 

간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다. 

 

두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)

 

두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.

 

이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.

 

두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.

 

정답 코드-1

import Foundation
let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
var arr = Array(repeating: -1, count: N)
var edges = [(u:Int, v:Int, cost:Int)]()
var edgeCost = 0
var comp = N
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))
}
let T = readLine()!.split(separator: " ").map{Int($0)!}
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){
let A = root(of: a)
let B = root(of: b)
if A==B{ return }
if T[A]+T[B] < cost+min(T[A], T[B]){ return }
arr[T[A] <= T[B] ? B:A] = T[A] <= T[B] ? A:B
edgeCost += cost
comp -= 1
}
edges.sort(by: {$0.cost > $1.cost})
while comp>1 && !edges.isEmpty{
let edge = edges.removeLast()
union(a: edge.u, b: edge.v, cost: edge.cost)
}
var warpCost = 0
for i in 0..<N{
if arr[i] < 0 {
warpCost += T[i]
}
}
print(min(warpCost+edgeCost, T.reduce(0, +)))
view raw 23743-1.swift hosted with ❤ by GitHub

정답 코드 - 2

import Foundation
let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
var visited = Array(repeating: false, count: N+1)
var arr = Array(repeating: -1, count: N+1)
var edges = [(u:Int, v:Int, cost:Int)]()
var edgeCost = 0
var comp = N+1
for _ in 0..<M{
let(u,v,c) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
edges.append((u,v,c))
}
let T = readLine()!.split(separator: " ").map{Int($0)!}
for i in 0..<N{
edges.append((0,i+1,T[i]))
}
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){
let A = root(of: a)
let B = root(of: b)
if A==B{ return }
arr[B] = A
edgeCost += cost
comp -= 1
}
edges.sort(by: {$0.cost > $1.cost})
while comp>1 && !edges.isEmpty{
let edge = edges.removeLast()
union(a: edge.u, b: edge.v, cost: edge.cost)
}
print(edgeCost)
view raw 23743-2.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[1765] 닭싸움 팀 정하기  (0) 2023.10.30
[23324] 어려운 모든 정점 쌍 최단 거리  (0) 2023.10.25
[1833] 고속도로 설계하기  (0) 2023.09.30
[16926] 배열 돌리기 1  (0) 2023.06.15
[3015] 오아시스 재결합  (0) 2023.06.12

+ Recent posts