[백준 kotlin] 1753 최단경로

문제

수열의 부분수열중 일정값을 넘는 부분수열의 가장 짧은 길이를 구한다.

---

풀이

최단거리를 구해야하기 때문에 다익스트라를 이용하였다.

 

먼저 우선순위 큐에 들어갈 데이터를 정의하였다.
데이터는 index와 거리가 필요하므로 다음과 같이 data class를 정의하였다.

data class Node(val index: Int, val distance: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int =
        distance - other.distance
}

distance값을 기준으로 정렬한다.

 

val (V, E) = readLine().split(" ").map { it.toInt() }
val K = readLine().toInt()
val distance = IntArray(V + 1) { Int.MAX_VALUE }.apply {  this[K - 1] = 0  }
val graph = MutableList(V) { PriorityQueue<Node>() }

repeat(E) {
    val (u, vv, w) = readLine().split(" ").map { it.toInt() }
    graph[u - 1].add(Node((vv - 1), w))
}

먼저 필요한 정보들을 선언한다.

distance는 무한으로 초기화하고

그래프를 선언하여 해당 간선의 정보를 입력받는다.

해당 코드에서는 그래프를 priority queue로 정의했지만 일반 배열로 정의해도 문제없다.

 

val pq = PriorityQueue<Node>().apply { offer(Node(K - 1, 0)) }

이후 pq를 선언한다. 실제 배열은 0부터 시작이기 때문에 index = k - 1, distance = 0이다.

 

while (pq.isNotEmpty()) {
        val now = pq.poll()
        if (now.distance > distance[now.index]) continue

        for (i in graph[now.index]) {
            val cost = i.distance + distance[now.index]
            val idx = i.index
            if (cost < distance[idx]) {
                distance[idx] = cost
                pq.offer(Node(idx, cost))
            }
        }
    }

다익스트라의 구현부이다. 

pq가 빌때까지 반복한다.

pq에서 index와 distance를 꺼내 now에 저장한다.

now의 거리 즉 now의 index까지 갈때 까지의 거리가 현재 저장되어있는 now의 인덱스 거리보다 크다면 의미가 없으므로 continue한다.

 

그렇지 않다면

now의 index의 간선 정보를 그래프에서 받아온다.

현재 위치까지의 거리와 다음위치까지의 거리를 더해 cost에 저장하고

다음 위치를 idx에 저장한다.

cost가 현재저장된 다음위치의 거리보다 작으면 갱신되야하므로 distance값을 갱신해주고

pq에 다음 위치의 Node정보를 저장한다.

 

해당 반복분이 끝나면 distance에는 최단거리가 저장되게 된다.

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.nio.Buffer
import java.util.ArrayList
import java.util.PriorityQueue
import kotlin.math.cos

data class Node(val index: Int, val distance: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int =
        distance - other.distance
}

fun main () = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (V, E) = readLine().split(" ").map { it.toInt() }
    val K = readLine().toInt()
    val distance = IntArray(V + 1) { Int.MAX_VALUE }.apply {  this[K - 1] = 0  }
    val graph = MutableList(V) { PriorityQueue<Node>() }

    repeat(E) {
        val (u, vv, w) = readLine().split(" ").map { it.toInt() }
        graph[u - 1].add(Node((vv - 1), w))
    }

    val pq = PriorityQueue<Node>().apply { offer(Node(K - 1, 0)) }


    while (pq.isNotEmpty()) {
        val now = pq.poll()
        if (now.distance > distance[now.index]) continue

        for (i in graph[now.index]) {
            val cost = i.distance + distance[now.index]
            val idx = i.index
            if (cost < distance[idx]) {
                distance[idx] = cost
                pq.offer(Node(idx, cost))
            }
        }
    }

    for (i in 0 until V) {
        if (distance[i] == Int.MAX_VALUE) println("INF")
        else println(distance[i])
    }

}