경험의 기록

문제

https://www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

 

풀이

0. 문제 해석

다익스트라 응용 문제이다.

 

두 정점을 반드시 지나는 최단경로는

 

  • 시작점 -> v1 -> v2 -> n
  • 시작점 -> v2 -> v1 -> n

 

두가지가 존재한다.

 

따라서 첫번째 경우엔

 

시작점 -> v1 / v1 -> v2 / v2 -> n

 

이런식으로 구간을 끊어서 다익스트라를 통해 최단거리를 구한 후

합산한다.

 

두번째도 동일하고, 그 두 루트중에 더 짧은 값이 최단거리이다.

 

여기서 INF를 INT의 MAX값으로 설정하면 MAX+MAX 연산에서 오류가 발생하는 케이스가 존재하므로,

 

간선의 최대 갯수가 200,000 개이고 최대 가중치가 1000이므로

200000 * 1000 보다 큰 값을 INF 로 설정하였다.

또한 양방향 그래프임에 주의한다.

 

 

 

1. 전체 코드

// [백준] 1504. 특정한 최단 경로 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

lateinit var dist: Array<Int>
lateinit var list: Array<ArrayList<Pair>>
const val INF = 200000001

data class Pair(val des: Int, val value: Int) : Comparable<Pair>{
    override fun compareTo(other: Pair): Int = value - other.value
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    var res1 = 0
    var res2 = 0

    val (n,e) = readLine().split(" ").map { it.toInt() }
    list = Array(n + 1) { arrayListOf()}
    dist = Array(n + 1) {INF}

    // 인접리스트 생성
    for(i in 0 until e){
        val (start, des, value) = readLine().split(" ").map {it.toInt()}
        list[start].add(Pair(des,value))
        list[des].add(Pair(start,value))
    }

    // 거쳐야 하는 점
    val (one, two) = readLine().split(" ").map { it.toInt() }

    // 시작점 -> v1 -> v2 -> n
    res1 += dijkstra(1, one)
    res1 += dijkstra(one, two)
    res1 += dijkstra(two, n)

    // 시작점 -> v2 -> v1 -> n
    res2 += dijkstra(1, two)
    res2 += dijkstra(two, one)
    res2 += dijkstra(one, n)

    // 둘 중 더 작은 경로
    var result = min(res1,res2)

    // 경로를 찾지 못한 경우
    if(result >= INF) {
        result = -1
    }
    println(result)
}

// 다익스트라
fun dijkstra(srt: Int, e: Int): Int{
    // 초기화
    Arrays.fill(dist, INF)

    val queue = PriorityQueue<Pair>()

    dist[srt] = 0 // 시작점 자신은 0
    queue.add(Pair(srt,0)) // 시작점 넣기

    while(queue.isNotEmpty()){
        val curIndex = queue.peek().des  // 현재 노드 인덱스
        val curValue = queue.peek().value  // 현재 노드까지의 거리
        queue.poll()

        if (dist[curIndex] < curValue) continue // 가중치가 더 큰 경로 탐색 X

        if(curIndex == e){
            break
        }
        // 인접리스트 탐색
        for (i in list[curIndex]) {
            val nextDes = i.des
            val nextValue = curValue + i.value

            // 최솟값 갱신
            if (nextValue < dist[nextDes]) {
                dist[nextDes] = nextValue
                queue.add(Pair(nextDes, nextValue))
            }
        }
    }

    return dist[e]
}
반응형

공유하기

facebook twitter kakaoTalk kakaostory naver band
loading