[백준][Kotlin]1753 최단경로

해당 문제는 다익스트라 알고리즘을 이용하여 작성 할 수 있습니다.

다익스트라 알고리즘은 노드별로 가중치가 있고 가중치가 0 이상의 양수 일 때 사용가능 하며, 출발 노드로 부터 특정 노드까지의 최단 거리를 구할 때 사용합니다.

 

작성 포인트로는

첫번째. 인접 리스트로 그래프 구현하기

두번째. 최단 거리 배열 초기화 하기

세번째. 값이 가장 작은 노드 고르기

네번째. 최간 거리 배열 업데이트 하기

 

두번째 포인트에 맞춰 최단 거리 배열을 초기화 할 때 추 후 값이 작은 값을 선택해야 하므로 그나마 무한대에 가까운 값을 넣어 초기화 합니다. 만약 입력값의 최대 범위가 Int 일 경우에는 Int.MAX_VALUE 로 초기화 하여도 됩니다.

세번째 포인트의 경우 우선순위큐를 이용하여 가중치가 적은 순 부터 비교하면 됩니다.

네번째 포인트의 경우 다음 노드의 가중치 혹은 거리를 구할 때 다음 노드가 가지고 있는 값과  현재 노드의 가중치 혹은 거리와 현재 노드부터 다음노드까지의 가중치 혹은 거리를 더한 값을 비교하여 작은 값으로 업데이트를 해주면 됩니다. 그리고 업데이트 시 해당 자료를 우선순위 큐에 넣어주면 됩니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val V = st.nextToken().toInt()
    val e = st.nextToken().toInt()
    st = StringTokenizer(br.readLine())
    val s = st.nextToken().toInt() // 출발노드
    val distance = IntArray(V+1){ Int.MAX_VALUE} // 거리 저장할 배열
    val visit = BooleanArray(V+1)
    val pq = PriorityQueue<Pair<Int,Int>>(kotlin.Comparator { o1, o2 ->  o1.first.compareTo(o2.first)})
    val nodelist = Array(V+1,{ArrayList<Info>()}) // 각 노드 별 갈 수 있는 정점 리스트

    repeat(e){
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt()
        val v = st.nextToken().toInt()
        val w = st.nextToken().toInt()
        nodelist[u].add(Info(v,w))
    }

    pq.add(Pair(0,s)) // 가중치,시작점
    distance[s] = 0
    while(!pq.isEmpty()){
        val Info = pq.poll()
        val now = Info.second// 현재 위치
        if(visit[now])continue
        visit[now] = true

        for(i in nodelist[now]){
            val next = i.target
            val value = i.current
            if(distance[next] > distance[now] + value){
            //만약 위에서 우선순위큐의 조건을 가중치가 적은순으로 하지 않았다면
            //가중치가 이상하게 꼬여 낮은 가중치를 가진 정보가 있더라도 높은게 들어가
            // 원하는 값이 아닌 다른 값이 나올 수 있음
            // ex) (2,30),(2,1),(2,2) 등등
                distance[next] = distance[now] + value
                pq.add(Pair(distance[next],next))
            }
        }
    }

    for(i in 1 .. visit.size-1){
        if(visit[i]) bw.appendLine(distance[i].toString())
        else bw.appendLine("INF")
    }
    
    bw.flush()
    bw.close()
}

data class Info(
    val target:Int, // 다음 정점
    val current:Int // 가중치
)