백준 1446) 지름길

문제

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

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

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

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

 

---

 

한창 bfs와 dfs 그래프 문제를 풀던 중에 다익스트라 알고리즘도 배우면 좋겠다 싶어서

Youtube에 나동빈 님께서 (이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘 영상을 보고 난 후에

적용시키고자 해당 문제를 풀어봤다.

정말 이해가 쏙쏙 되니 평소 다익스트라 알고리즘에 이해가 잘 가지 않는다면 아래 링크를 참조하면 좋을 듯 하다!

 

 

https://youtu.be/acqm9mM1P6o

(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘

 

접근 방법

 

위 문제는 전형적인 다익스트라 알고리즘 + 약간의 응용을 요구하고 있었다.

핵심 아이디어는 다음과 같았다.

 

• 차를 타고 고속도로를 지나야 학교에 도착하므로, 출발은 항상 0이다. ( 0 <= d <= 10000)
• 단, 지름길이 고속도로 길이 d보다 크다면 역주행은 할 수 없기 때문에 무시한다.
• 0부터 d까지 1씩 증가하되 minOf(현재 거리를 담는 배열의 값, 1씩 증가시킨 값) 으로 비교해야 지름길을 표현할 수 있다.

 

 

 

핵심 아이디어를 중점으로 다음의 로직으로 구성했다.

 

1. 거리 배열(dist)을 무한대 값으로 초기화

 

2. dist[0] = 0 으로 할당

 

3. for 문으로 0부터 고속도로의 길이(d) 까지 반복

 

- dist[i] = minOf(dist[i], dist[i-1] + 1) 로 현재 배열의 값이 지름길로 거쳐왔다면 더 작은 값이므로 이를 분별하기 위해 작성된 코드

- 단, i=0 일 때는 dist[i-1] 에 접근할 수 없으므로 if(i != 0) 이라는 방호 코드를 작성

 

 

4. 역주행을 막기 위해 지름길의 끝 지점이 고속도로의 길이(d) 보다 크다면 continue

 

 

위의 로직은 다익스트라 알고리즘에서 추가된 것만 정리한거고

다익스트라 알고리즘에 쓰이는 문법 구조의 설명은 주석을 참고하면 되겠다.

 

 

 

전체 코드

 

import java.util.*
import kotlin.collections.ArrayList

//무한대를 설정하기 위해 Int의 최대 범위인 2147483647 이용
const val INF = Int.MAX_VALUE

//인접리스트 형태로 그래프 그리기
private val g = Array(10001) { ArrayList<Node>()}
val dist = IntArray(10001) { INF}
var n = 0
var d = 0
fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine().split(" ").map { it.toInt() }
    n = input[0]
    d = input[1]

    repeat(n) {
        val (x,y,s) = readLine().split(" ").map { it.toInt() }
        g[x].add(Node(s,y))
    }

    dijkstra()
}

private fun dijkstra() {
    val pq = PriorityQueue<Node>()
    //0에서부터 출발하므로 0 대입
    dist[0] = 0

    for(i in 0..d) {
        if(i!=0)
            dist[i] = minOf(dist[i],dist[i-1] + 1)

	//만약 그래프에 i에 지름길이 포함돼있다면 다익스트라 이용하기
        if(g[i].isNotEmpty()) {
            pq.add(Node(dist[i],i))

            while (pq.isNotEmpty()) {
                val (distance, now) = pq.poll()!!

		//distance가 더 크다는 것은 이미 해당 노드를 방문한 것
                //e.g.
                // 1 -> 2로 갈 때 거리가 3이고, 1 -> 3으로 갈 때 거리가 2
                // 2 -> 3으로 갈 때 거리가 1이라면
                // 1 -> 2 -> 3 은 4, 1 -> 3이 2 인데
                // 우선순위 큐에 따라 2가 먼저 저장되므로
                // 4 > 2에 의해 성립
                if(distance > dist[now]) continue

		//노드에 연결된 다른 노드들 방문
                for(next in g[now]) {
               	// 다음 노드가 고속도로 길이보다 클 경우 무시
                    if(next.idx > d) continue

			// 현재 거리 + 다음 노드의 거리
                    val cost = distance + next.dist
                    // 거리 배열에 최솟값일 때 저장한다는 의미
                    if(cost < dist[next.idx]) {
                        pq.add(Node(cost, next.idx))
                        dist[next.idx] = cost
                    }
                }
            }
        }
    }
    println(dist[d])
}

private data class Node(
    val dist : Int, // 거리
    val idx : Int	// 고속도로 거리의 현재 지점
) : Comparable<Node> {
	// PriorityQueue에서 거리에 대해 최소 힙을 정해야 하기 때문에
    // Comparable<Node> 인터페이스를 상속
    // **이걸 하지 않으면 오류 뜸!
    override fun compareTo(other: Node): Int {
        return this.dist.compareTo(other.dist)
    }
}