https://www.acmicpc.net/problem/3271
번역기능으로 문제를 봐도 이해되지 않아 헤맸다. chatGPT를 통해 번역과 설명을 보고 나서 이해하여 정답을 받았다..
기본적인 최소 스패닝 문제.
풀이 방법
B마리의 벌들이 F개의 꽃을 최소 스패닝 트리로 구성하여 각 구역을 분담하여 탐색하게 된다. 이때 각 벌들이 분담받은 이동 경로 중 한 번에 가장 많이 이동한 거리의 최솟값을 출력하라는 얘기.
따라서 크루스칼 알고리즘을 컴포넌트가 B개가 될 때까지 진행하고, 이때까지 가장 많이 이동한 거리를 출력하면 된다.
정답 코드
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 (F,B) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0] | |
| var flower = [(x:Int, y:Int)]() | |
| var arr = Array(repeating: -1, count: F) | |
| var edges = [(u:Int, v:Int, cost:Double)]() | |
| var ans:Double = 0 | |
| var comp = F | |
| for _ in 0..<F{ | |
| let (x,y) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0] | |
| flower.append((x,y)) | |
| } | |
| func cost(from u:(x:Int, y:Int), to v:(x:Int, y:Int)) -> Double { | |
| return sqrt(pow(Double(u.x - v.x), 2) + pow(Double(u.y - v.y), 2)) | |
| } | |
| func rootOf(node:Int) -> Int{ | |
| if arr[node]<0 {return node} | |
| arr[node] = rootOf(node: arr[node]) | |
| return arr[node] | |
| } | |
| func union(a:Int, b:Int, cost:Double){ | |
| let ra = rootOf(node: a) | |
| let rb = rootOf(node: b) | |
| if ra==rb { return } | |
| arr[rb] = ra | |
| ans = max(ans, cost) | |
| comp -= 1 | |
| } | |
| for i in 0..<F-1{ | |
| for k in i+1..<F{ | |
| edges.append((i,k,cost(from: flower[i], to: flower[k]))) | |
| } | |
| } | |
| edges.sort(by: {$0.cost > $1.cost}) | |
| while comp>B && !edges.isEmpty{ | |
| let edge = edges.removeLast() | |
| union(a: edge.u, b: edge.v, cost: edge.cost) | |
| } | |
| print(String(format: "%.2f", round(ans*100)/100)) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [17208] 카우버거 알바생 (0) | 2024.09.11 |
|---|---|
| [7211] Ringsõit (1) | 2024.06.09 |
| [17090] 미로 탈출하기 (0) | 2024.04.24 |
| [14923] 미로 탈출 (0) | 2024.04.21 |
| [13397] 구간 나누기 2 (0) | 2024.02.28 |