[코틀린] 백준 10217번 : KCM Travel 문제풀이
풀이
다익스트라에 동적프로그래밍(DP) 개념이 들어간 문제입니다..
일반적인 다익스트라와 달리, 이 문제는 비용이라는 매개변수녀석이 추가적으로 들어갑니다.
그러나 초기 문제를 해석할 때 그냥 일반 다익스트라로 풀 수 있을줄 알았습니다.
fun dijkstra(start: Int, dst: IntArray, M: Int, N: Int, nodeList: Array<ArrayList<Node>>): Int {
val isVisited = BooleanArray(N + 1)
val q = PriorityQueue<Node>()
Arrays.fill(dst, INF)
q.offer(Node(start, 0, 0))
dst[start] = 0
while (!q.isEmpty()) {
val cur: Node = q.poll()
if (isVisited[cur.end]) continue
isVisited[cur.end] = true
for (next in nodeList[cur.end]) {
if (dst[next.end] > dst[cur.end] + next.weight && cur.cost + next.cost <= M) {
q.offer(Node(next.end, dst[next.end], cur.cost + next.cost))
dst[next.end] = dst[cur.end] + next.weight
}
}
}
return dst[N]
}
요딴식으로 말이죠.
비용에 대한 고려를 다음노드에 가는 총비용이 M을 초과할 경우에 스킵하는 로직
으로 짰으나 시원하게 틀렸습니다가 나왔습니다.
질문 게시판에 찾아가 보니 좋은 반례가 있었습니다.
1
6 149 8
1 2 60 20
2 3 30 70
1 3 100 80
1 3 20 180
3 4 20 100
3 5 150 20
5 6 50 40
4 6 30 50
ans: 240
wrong: Poor KCM
이 반례인데요, 보기 쉽게 그림으로 그려봅시다.
여기에서 만약, 답으로 가는 길을 구한다면 다음과 같이 그릴 수 있습니다.
저는 비용 1번 공항에서 2번을 거쳐 3번 공항으로 가고 싶은데, 그땐 이미 dst[3]은 최소거리인 80으로 갱신되어 못가게 됩니다.
이 로직 오류를 방지하기 위해 dst 배열을 2차원으로 dst[도착노드][소요비용] 의 형식으로 2차원 배열로 구성하면 됩니다.
그렇게 된다면 20의 비용으로 3번을 가는 거리를 따로 갱신할 수 있어 정확한 정답을 구할 수 있게됩니다.
Source Code
package 다익스트라.`10217번_KCM Travel`
import java.util.*
const val INF = 1_000_000_000
fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
val sb = StringBuilder()
repeat(readLine().toInt()) {
val (N, M, K) = readLine().split(" ").map { it.toInt() }
val nodeList = Array(N + 1) { ArrayList<Node>() }
val dst = Array(N + 1) { IntArray(M + 1) }
repeat(K) {
val (u, v, c, d) = readLine().split(" ").map { it.toInt() }
nodeList[u].add(Node(v, d, c))
}
val answer = dijkstra(1, dst, M, N, nodeList)
sb.append("$answer \n")
}
print(sb)
}
fun dijkstra(start: Int, dst: Array<IntArray>, M: Int, N: Int, nodeList: Array<ArrayList<Node>>): String {
val q = PriorityQueue<Node>()
for (element in dst) {
Arrays.fill(element, INF)
}
q.offer(Node(start, 0, 0))
dst[start][0] = 0
while (!q.isEmpty()) {
val cur: Node = q.poll()
// 현재 노드가 LA라면 지금 현재 거리를 출력 (우선순위 큐를 사용했으므로 무조건 최소 거리가 된다.)
if (cur.end == N) return cur.weight.toString()
for (next in nodeList[cur.end]) {
val nextCost = cur.cost + next.cost
if (nextCost > M) continue // 돈을 허용치 초과할 시 continue
// next 노드를 'nextCost' 비용으로 가는 현재의 거리가 더 짧다면 갱신을 한다.
if (dst[next.end][nextCost] > cur.weight + next.weight) {
dst[next.end][nextCost] = cur.weight + next.weight
q.offer(Node(next.end, dst[next.end][nextCost], cur.cost + next.cost))
}
}
}
return "Poor KCM"
}
data class Node(val end: Int, val weight: Int, val cost: Int) : Comparable<Node> {
override fun compareTo(other: Node): Int = weight - other.weight
}
마치.. 여러 경우를 고려해야하는 2차원 행렬에서의 BFS로직의 isVisited를 다차원(3차원 이상) 배열로 구성하는 것과 비슷한 논리네요.
좋은 다익스트라의 응용에 대한 공부가 될 수 있는 문제였습니다.
Author And Source
이 문제에 관하여([코틀린] 백준 10217번 : KCM Travel 문제풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@blucky8649/코틀린-백준-10217번-KCM-Travel-문제풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)