[Kotlin] BOJ1238 파티

링크 :https://www.acmicpc.net/problem/1238

1238번: 파티

 

◆ 이번 문제에서 오답포인트

문제를 풀 때 X마을에 사는 친구의 X마을까지의 최단거리는 0인데,
다익스트라 함수에 X를 놓고 돌려버려서 오답이 나왔었다.
(X마을에서 굳이 다른 마을까지 가서 X마을까지 도달하는 최단거리를 갱신하고 있었던 것)
해당 문제에 33퍼에서 오답이 나오시는 분들은 이 내용을 참고해서 디버깅해보시길 바랍니다.

 

◆ 추가로 깨달은 점
A노드가 B노드와 연결이 되어있나 라는식의 검사식이 필요하지 않다면 (이 경우엔 인접행렬이 인접리스트보다 빠름)
웬만하면 인접행렬보단 인접리스트를 사용하자 (인접행렬 사용 시 연결된 노드 검색시간이 많이 듬)

 

◆ ETC

저는 다익스트라를 노드의 개수(V)만큼 돌리는 방식으로 구현을 했는데

다른 분 코드를 보니 다들 간선 방향을 뒤집어서   

모든 노드 -> X노드  최단거리를   =  간선 뒤집힌 그래프에서 X노드 -> 모든 노드의 최단거리

인 성질을 이용해서 V번의 다익스타를 돌리는게 아닌 한 번의 다익스트라로 값을 구하는 방식으로 

푸셨다는 점 참고하시길..(시간 복잡도,메모리사용량 면에서도 이 방법이 훨씬 좋아보입니다..)

---

소스코드(dijkstra)

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.util.*

private var N = 0 // (1 ≤ N ≤ 1,000) //마을, 학생의 수
private var M = 0 // (1 ≤ M ≤ 10,000) // 도로의 개수
private var X = 0 // (1 ≤ X ≤ N) // 모이기로한 마을
//각 도로간 걸리는 시간 T (1 ≤ T ≤ 100)
private lateinit var map : List<MutableList<Node>>
private lateinit var answerList :MutableList<Int>
private lateinit var minimumTimeList :MutableList<Int>
private fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    X= st.nextToken().toInt()
    map = List(N+1){ mutableListOf() }
    minimumTimeList = MutableList(N+1){ Int.MAX_VALUE }
    answerList = MutableList(N+1){0}

    repeat(M){
        val(a,b,c) = br.readLine().split(" ").map{ it.toInt() }
        map[a].add(Node(b,c))
    }

    //각 지점에서 X로 가는 최단거리
    for (i in 1 .. N){
        if (i == X) continue // X에서 X까지의 최단거리는 0임으로
        dijkstra(i)
        answerList[i] += minimumTimeList[X]
        minimumTimeList = MutableList(N+1){ Int.MAX_VALUE }
    }

    //X에서 각 지점으로 돌아가는 최단거리
    dijkstra(X)
    for (i in 1 ..N){
        if (i == X) continue
        answerList[i] += minimumTimeList[i]
    }

    println(answerList.maxOf { it })
}

private fun dijkstra(start :Int){
    val PQ = PriorityQueue<Node>()
    PQ.add(Node(start,0))
    while(PQ.isNotEmpty()){
        val node = PQ.poll()
        if (minimumTimeList[node.num] < node.time) continue
        for (nextNode in map[node.num]){
            val cost = node.time + nextNode.time
            if (cost < minimumTimeList[nextNode.num]){
                minimumTimeList[nextNode.num] = cost
                PQ.add(Node(nextNode.num,cost))
            }
        }
    }
}

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