https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
다익스트라 알고리즘으로 접근한 문제다. 힙 구현이 필요하다. 직접 구현할 역량이 안되기에, Rhyno님이 작성한 힙을 사용하였다.
풀이
간선과 가중치를 입력받은 map 배열을 통해, 다익스트라 알고리즘을 사용한다. 양방향 간선이 아닌 단방향 간선이기에 우선 파티 장소 x에서 각 마을로 되돌아가는 배열을 생성, 다익스트라 알고리즘을 통해 각 인덱스에 저장. 이후 1 ~ n번 마을에서 x로 향하는 최단거리를 한 번 더 다익스트라 알고리즘을 통해 방금 저장한 배열에 추가시켜 준다. 마지막으로 배열에 담긴 최댓값을 출력한다.
정답 코드
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 | |
| //heap by rhyno | |
| public struct Heap<T> { | |
| var nodes: [T] = [] | |
| let comparer: (T,T) -> Bool | |
| var isEmpty: Bool { | |
| return nodes.isEmpty | |
| } | |
| init(comparer: @escaping (T,T) -> Bool) { | |
| self.comparer = comparer | |
| } | |
| func peek() -> T? { | |
| return nodes.first | |
| } | |
| mutating func insert(_ element: T) { | |
| var index = nodes.count | |
| nodes.append(element) | |
| while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) { | |
| nodes.swapAt(index, (index-1)/2) | |
| index = (index-1)/2 | |
| } | |
| } | |
| mutating func delete() -> T? { | |
| guard !nodes.isEmpty else { | |
| return nil | |
| } | |
| if nodes.count == 1 { | |
| return nodes.removeFirst() | |
| } | |
| let result = nodes.first | |
| nodes.swapAt(0, nodes.count-1) | |
| _ = nodes.popLast() | |
| var index = 0 | |
| while index < nodes.count { | |
| let left = index * 2 + 1 | |
| let right = left + 1 | |
| if right < nodes.count { | |
| if comparer(nodes[left], nodes[right]), | |
| !comparer(nodes[right], nodes[index]) { | |
| nodes.swapAt(right, index) | |
| index = right | |
| } else if !comparer(nodes[left], nodes[index]){ | |
| nodes.swapAt(left, index) | |
| index = left | |
| } else { | |
| break | |
| } | |
| } else if left < nodes.count { | |
| if !comparer(nodes[left], nodes[index]) { | |
| nodes.swapAt(left, index) | |
| index = left | |
| } else { | |
| break | |
| } | |
| } else { | |
| break | |
| } | |
| } | |
| return result | |
| } | |
| } | |
| extension Heap where T: Comparable { | |
| init() { | |
| self.init(comparer: <) | |
| } | |
| } | |
| let nmx = readLine()!.split(separator: " ").map{Int($0)!} | |
| let n = nmx[0] | |
| let m = nmx[1] | |
| let x = nmx[2]-1 | |
| var map = Array(repeating: [(Int,Int)](), count: n) | |
| for _ in 0..<m{ | |
| let info = readLine()!.split(separator: " ").map{Int($0)!} | |
| let u = info[0]-1 | |
| let v = info[1]-1 | |
| let cost = info[2] | |
| map[u].append((v,cost)) | |
| } | |
| for i in 0..<n{ | |
| map[i].sort(by: { $0.1 < $1.1 }) | |
| } | |
| func dij(from a:Int) -> [Int]{ | |
| var q = Heap<(Int,Int)>(comparer: { $0.1 > $1.1 }) | |
| var visited = Array(repeating: false, count: n) | |
| var result = Array(repeating: -1, count: n) | |
| result[a] = 0 | |
| q.insert((a,0)) | |
| while !q.isEmpty{ | |
| let curr = q.delete()! | |
| let idx = curr.0 | |
| if !q.isEmpty && visited[idx]{ continue } | |
| visited[idx] = true | |
| for next in map[idx]{ | |
| if (result[next.0] == -1) || (result[next.0] > result[idx] + next.1){ | |
| result[next.0] = result[idx] + next.1 | |
| q.insert((next.0,result[next.0])) | |
| } | |
| } | |
| } | |
| return result | |
| } | |
| var ans = dij(from: x) | |
| for i in 0..<n{ | |
| ans[i] += dij(from: i)[x] | |
| } | |
| print(ans.max()!) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [2018] 수들의 합 5 (0) | 2023.01.11 |
|---|---|
| [1504] 특정한 최단 경로 (0) | 2023.01.04 |
| [2056] 작업 (0) | 2023.01.02 |
| [14567] 선수과목 (0) | 2023.01.01 |
| [1584] 게임 (0) | 2022.12.30 |