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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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, +))) |
정답 코드 - 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) |
'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 |