[알고리즘] 특정한 최단 경로 (백준 1504번)

1504번: 특정한 최단 경로

 그래프 이론 문제로 1번 노드에서 N번 노드까지의 최단 거리를 구해야 하는데 중간에 V1, V2에 해당하는 노드들을 꼭 거쳐가야 한다. 

 

Solution

 우선 문제에서 유추할 수 있는 것을 찾아본다면

1. 가중 그래프에서의 최단 경로
   1. 다익스트라, 플로이드 와샬 예상
2. 무향 그래프
   1. 위상 정렬은 사용 불가 (사이클 o)
3. v1, v2를 무조건 거쳐야 함 (나올 수 있는 최단 경로의 수는 2개)
   
   1. 1 → v1 → v2 → N
   2. 1 → v2 → v1 → N

 결론적으로 시작 노드를 1, v1, v2로 하는 다익스트라 알고리즘을 3번 돌려서 나올 수 있는 최단 경로의 수 2가지 중 거리가 가장 짧은 것을 출력하면 된다.

 만약 v1, v2를 모두 거쳐서 갈 수 없다면 -1을 출력한다. (2가지 최단 경로 둘다 중간에 INF인 것이 있다면 -1 출력)

 

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

import kotlin.collections.ArrayList
import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var graph : ArrayList<ArrayList<Edge>> = ArrayList()
lateinit var dist : Array<Array<Int>>
val INF = 200000001 //20000 * 1000 + 1
var v1 = 0
var v2 = 0
var N = 0
var E = 0
//dist[1] dist[v1] dist[v2]

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    N = strtok.nextToken().toInt()
    E = strtok.nextToken().toInt()

	//1번 노드, V1 노드, V2노드에서의 최단거리 보관
    dist = Array(3, { Array(N + 1,{INF}) })
	//0 : 1번, 1 : V1, 2 : V2
    
    for(i in 0 .. N)
        graph.add(ArrayList())

    for(i in 0 until E)
    {
        strtok = StringTokenizer(br.readLine())
        var a = strtok.nextToken().toInt()
        var b = strtok.nextToken().toInt()
        var c = strtok.nextToken().toInt()

        graph.get(a).add(Edge(a, b, c))
        graph.get(b).add(Edge(b, a, c))
    }

    strtok = StringTokenizer(br.readLine())
    v1 = strtok.nextToken().toInt()
    v2 = strtok.nextToken().toInt()

	//dist들을 초기화
    //1 -> v1, 1->v2
    graph.get(1).forEach { edge ->
        if(edge.to == v1)
        {
            dist[0][v1] = edge.weight
            dist[1][1] = edge.weight
        }
        else if(edge.to == v2)
        {
            dist[0][v2] = edge.weight
            dist[2][1] = edge.weight
        }
    }

    //v1 -> v2, v1 -> N
    graph.get(v1).forEach { edge ->
        if(edge.to == v2)
        {
            dist[1][v2] = edge.weight
            dist[2][v1] = edge.weight
        }
        else if(edge.to == N)
        {
            dist[1][N] = edge.weight
        }
    }

    //v2 -> N
    graph.get(v2).forEach { edge ->
        if(edge.to == N)
            dist[2][N] = edge.weight
    }


    dijkstra(1)
    dijkstra(v1)
    dijkstra(v2)

	//경로 중 INF인 것이 있다면 1->N까지 못감, 만약 경로 2개다 못간다면 -1 출력
    if((dist[0][v1] == INF || dist[1][v2] == INF || dist[2][N] == INF) 
    	&& (dist[0][v2] == INF || dist[2][v1] == INF || dist[1][N] == INF))
    {
        bw.write("-1")
        return
    }

    var min1 = dist[0][v1] + dist[1][v2] + dist[2][N]
    var min2 = dist[0][v2] + dist[2][v1] + dist[1][N]

    bw.write(min(min1, min2).toString())
}


fun dijkstra(start: Int)
{
    var index = 0

//index 매핑
    when(start)
    {
        1 -> index = 0
        v1 -> index = 1 //v1
        v2 -> index = 2//v2
    }

    dist[index][start] = 0

    var queue = PriorityQueue<Node>({o1, o2 -> o1.dist - o2.dist})
    queue.offer(Node(start, 0))
    
    var visited = BooleanArray(N + 1)

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.num])
            continue
        visited[now.num] = true

        for(next in graph.get(now.num))
        {
            if(dist[index][next.to] > dist[index][now.num] + next.weight)
            {
                dist[index][next.to] = dist[index][now.num] + next.weight
                queue.offer(Node(next.to, dist[index][next.to]))
            }
        }
    }
}

data class Edge(var from : Int, var to : Int, var weight : Int)
data class Node(var num : Int, var dist : Int)

fun main() {
    solution()


    br.close()
    bw.close()
}