백준 1446 - 지름길(Kotlin)

1446번: 지름길

1446번: 지름길

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다.

이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

 

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

---

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다.

N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다.

다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다.

모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

---

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

---

알고리즘 분류

• 다이나믹 프로그래밍(DP)
• 그래프 이론
• 다익스트라(Dijkstra)
• 최단 경로

---

해설

이번 문제는 다익스트라(Dijkstra) 알고리즘을 이용하여 해결해야 한다.

 

이 문제는 다익스트라의 기본만 알면 해결할 수 있다.

예전에 블로그에 설명한 글과 다익스트라를 이용한 알고리즘 해설을 올린적 있기에 자세한 설명은 하지 않겠다.

 

나의 풀이는 아래와 같다.

 

우선 2차원 배열 graph 를 선언했다. 해당 그래프에는 다음노드, 현재노드에서 다음 노드까지의 거리 가 담겨있다.

 

for (i in 0 until destination) {
    graph[i].add(Node1446(i + 1, 1))
}

 

위의 코드가 초기화 하는 부분이다.

 

그리고 거리가 담겨있는 1차원 배열 distance 를 선언해주었고 INF 값으로 초기화해주었다.

그 후 입력받은 지름길을 graph 에 추가해야 한다.

 

여기서 주의할 점은 지름길 도착위치 - 시작위치 < 지름길 거리 라면 지름길을 이용하는 것이 더 비효율적이기에 추가하지 않는다.

또한 지름길 도착위치 > 최종 이동 위치 여도 문제 특성상 후진이 불가능하므로 추가하지 않는다.

 

그 후 다익스트라 알고리즘을 실행한다.

 

다익스트라 알고리즘은 아래와 같은 로직을 수행한다.

• 우선순위 큐 pq 를 선언하고 노드번호 기준으로 오름차순으로 정렬되게 한다.
• pq 에 (시작위치, 0)을 넣고 distance[0] = 0 으로 초기화한다.
• pq 가 빌 때까지 반복문을 수행한다.
  • pq 에서 값을 꺼낸다. (cNode, cDist)
  • distance[cNode] < cDist 라면 이미 최단경로를 구한 것이기에 continue 한다.
  • 위의 경우가 아니라면 다음 노드(nNode, nDist) 까지의 거리를 구한다.
    dist = (cDist + nDist)
  • dist < distance[nNode] 즉, 방금 구한 다음 노드까지의 거리가 distance 에 저장된 값보다 작다면 pq 에 추가하고 distance 를 최신화 한다.

---

전체 코드

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

private data class Node1446(val node: Int, val dist: Int) : Comparable<Node1446> {
    override fun compareTo(other: Node1446): Int = dist - other.dist
}

lateinit var distance: Array<Int>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (cnt, destination) = br.readLine().split(" ").map { it.toInt() }
    distance = Array(destination + 1) { Int.MAX_VALUE }
    val graph = Array<MutableList<Node1446>>(destination + 1) { mutableListOf() }

    //i번째 노드에서 다음 노드(i + 1) 까지의 거리는 1을 의미한다.
    for (i in 0 until destination) {
        graph[i].add(Node1446(i + 1, 1))
    }

    repeat(cnt) {
        val (s, d, l) = br.readLine().split(" ").map { it.toInt() }

        //만약 지름길 도착위치 - 시작 위치가 지름길 거리보다 크다면 지름길을 이용하는 것이 더 비효율 적이다.
        //또한 도착위치 > 최종위치라면 후진이 불가능하므로 추가하지 않는다.
        if (d - s > l && d <= destination) {
            graph[s].add(Node1446(d, l))
        }
    }

    dijkstra(graph)
    println(distance[destination])

}

private fun dijkstra(graph: Array<MutableList<Node1446>>) {
    val pq = PriorityQueue<Node1446>()
    distance[0] = 0
    pq.add(Node1446(0, 0))

    while (pq.isNotEmpty()) {
        // 현재 노드, 현재 노드까지의 거리
        val (cNode, cDist) = pq.poll()

        //이미 갱신되어 있다는 뜻이다.
        if (distance[cNode] < cDist) {
            continue
        }

        graph[cNode].forEach {
            //다음 노드, 다음노드 까지의 거리
            val (nNode, nDist) = it

            //현재 노드까지의 거리 + 다음 노드까지의 거리
            val dist = cDist + nDist

            if (dist < distance[nNode]) {
                pq.add(Node1446(nNode, dist))
                distance[nNode] = dist
            }
        }
    }
}

 

---

정답

 

요즘 dp 문제 적응하려고 실버문제들 풀고있는데 갑자기 다익스트라 문제가 나와서 당황했다…

분명 분류에 dp문제로 검색했는데…..🥺