[백준][Kotlin]1948번 임계경로

해당 문제는 위상정렬의 개념을 이해하고 위상정렬을 이용하여 걸리는 시간을 구한 뒤 해당 로직을 반대로 돌리면서 1분도 쉬지 않고 달려야 하는 도로의 수를 구해야 하는 문제였습니다.

단순히 도시에 도착하기까지 걸리는 시간은 단순히 위상정렬을 이용하여 구할 수 있지만, 해당 로직을 어떻게 반대로 돌려야 하는지 헷갈릴 수 있습니다.

 

해당 문제 작성 시 포인트로는 해당 도시에서 갈 수 있는 경로를 구할 때 배열을 2개를 생성하여 첫번째 배열에는 정방향 일때 두번째는 역방향 일때의 경로를 저장하여 추후 로직을 반대로 돌릴 때 이용합니다.

 

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

 

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 n = st.nextToken().toInt()
    st = StringTokenizer(br.readLine())
    val m = st.nextToken().toInt()

    var ar = Array(n+1,{ArrayList<Info>()}) // 도시 인접 리스트
    var arreverse =Array(n+1,{ArrayList<Info>()}) // 역방향 도시 인접 리스트 -> 추후 1분도 쉬지 않고 달려야 하는 도로의 수 찾을 때 사용
    var indegree = IntArray(n+1){0} // 진입 차수 배열

    repeat(m){
        st = StringTokenizer(br.readLine())
        val start = st.nextToken().toInt()
        val end = st.nextToken().toInt()
        val time = st.nextToken().toInt()

        ar[start].add(Info(end,time))
        arreverse[end].add(Info(start,time))
        indegree[end]++
    }

    st = StringTokenizer(br.readLine())

    var startcity = st.nextToken().toInt() // 출발하는 도시
    var endcity = st.nextToken().toInt() // 도착하는 도시

    var dq = ArrayDeque<Int>()
    dq.add(startcity)
    var result = IntArray(n+1)
    while(!dq.isEmpty()){
        val now = dq.pollFirst()
        for(i in ar[now]){
            indegree[i.targetNode]--
            result[i.targetNode] = Math.max(result[i.targetNode],result[now]+i.value) // 최장 시간
            if(indegree[i.targetNode] == 0){
                dq.addLast(i.targetNode)
            }
        }

    }

    var resultCount = 0
    var visit = BooleanArray(n+1)
    dq = ArrayDeque<Int>()
    dq.add(endcity)
    visit[endcity] = true

    while(!dq.isEmpty()){
        val now = dq.pollFirst()
        for(i in arreverse[now]){
            if(result[i.targetNode] + i.value == result[now]){ // 해당 도시의 시간을 구할 때 최장시간으로 저장하였었음 그렇기에 해당 도시만 구하는 과정
                resultCount++
                if(visit[i.targetNode] == false){ //갔던 도시 다시 돌아가기 방지
                    visit[i.targetNode] = true
                    dq.addLast(i.targetNode)
                }
            }
        }
    }

    println(result[endcity])
    println(resultCount)

    //bw.flush()
    //bw.close()
}

data class Info(
    var targetNode:Int,
    var value:Int
)