https://www.acmicpc.net/problem/9370
난이도 : 골드 2
태그 : 데이크스트라, 그래프 이론
설명
다익스트라를 응용한 문제입니다.
S에서 시작하여, G - H 혹은 H - G 구간을 거쳐, t1, t2, t3, 총 3개의 목적지 후보로 갈 수 있다 가정해보겠습니다.
이 때, 시작점인 S와 목적지인 T1의 최단거리가
S - G - H - T1 혹은 S - H - G - T1 과 같을 때, T1은 가능한 목적지 경로입니다.
S - G - H - T2, S - H - G - T2 모두 S - T2 와 같지 않으면, 이는 불가능한 목적지 경로입니다.
즉, 모든 목적지 T에 대해
다익스트라를 사용하여
(S-G 최단경로) + (G-H 최단경로) + (H-T 최단경로) 또는
(S-H 최단경로) + (H-G 최단경로) + (G-T 최단경로)가
(S-T 최단경로) 와 같은지 확인하면 됩니다.
소스코드
import java.util.*
import kotlin.collections.ArrayList
class Node(val index: Int, val cost: Int) : Comparable<Node> {
override fun compareTo(other: Node): Int {
return (this.cost - other.cost)
}
}
var n = 0
var m = 0
var t = 0
var s = 0
var g = 0
var h = 0
lateinit var graph: Array<ArrayList<Node>>
lateinit var candidate: Array<Int>
fun main() = with(System.`in`.bufferedReader()) {
val sb = StringBuilder()
repeat(readLine().toInt()) {
var st = StringTokenizer(readLine())
n = st.nextToken().toInt()
m = st.nextToken().toInt()
t = st.nextToken().toInt()
// s - 예술가 출발지, g - h 구간
st = StringTokenizer(readLine())
s = st.nextToken().toInt()
g = st.nextToken().toInt()
h = st.nextToken().toInt()
graph = Array(n + 1) { ArrayList<Node>() }
repeat(m) {
st = StringTokenizer(readLine())
val (a, b, d) = Array(3) { st.nextToken().toInt() }
graph[a].add(Node(b, d))
graph[b].add(Node(a, d))
}
// 목적지 후보들
candidate = Array(t) { readLine().toInt() }.sortedArray()
val goals = ArrayList<Int>()
// 다익스트라
candidate.forEach { target ->
val shortestLength = dijkstra(s, target)
val path1 = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, target)
val path2 = dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, target)
if (shortestLength == path1 || shortestLength == path2) {
goals.add(target)
}
}
goals.sorted().forEach {
sb.append(it).append(" ")
}
sb.append("\n")
}
print(sb)
}
fun dijkstra(start: Int, end: Int): Int {
val dist = Array(n + 1) { Int.MAX_VALUE }
dist[start] = 0
val pq = PriorityQueue<Node>()
pq.offer(Node(start, 0))
while (pq.isNotEmpty()) {
val nowNode = pq.poll()
if (nowNode.cost > dist[nowNode.index]) continue
graph[nowNode.index].forEach { nextNode ->
if (dist[nextNode.index] > nowNode.cost + nextNode.cost) {
dist[nextNode.index] = nowNode.cost + nextNode.cost
pq.offer(Node(nextNode.index, nowNode.cost + nextNode.cost))
}
}
}
return dist[end]
}
후기
다익스트라를 응용하여 풀 수 있었던 문제였습니다.
평소 우선순위 큐를 사용한 다익스트라를 잘 해보지 않아 좀 어색했지만,
이제 조금 익숙해져가네요.
'코딩테스트 > Kotlin' 카테고리의 다른 글
[백준 4458번] [Kotlin] 첫 글자를 대문자로 (0) | 2023.03.29 |
---|---|
[백준 2902번] [Kotlin] KMP는 왜 KMP일까? (0) | 2023.03.28 |
[백준 12891번] [Kotlin] DNA 비밀번호 (0) | 2023.03.27 |
[백준 26517번] [Kotlin] 연속인가?? (0) | 2023.03.26 |
[백준 1010번] [Kotlin] 다리 놓기 (0) | 2023.03.26 |