백준 22870 산책 (large) Kotlin (다익스트라)

문제 출처 : https://www.acmicpc.net/problem/22870

22870번: 산책 (large)

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 간 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 짧은 거리와 E에서 S로 가는 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1번째 줄까지 정점 A,B가 공백으로 구분되어 주어진다. 정점 A와 정점 B 사이의 거리는 항상 1이다. 이때, 정점 A와 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

출력

산책의 전체 경로의 길이를 출력한다.

제한

1 -> 2 -> 4 -> 3 -> 1 순서대로 오면 된다.

알고리즘 분류

• 그래프 이론
• 다익스트라

풀이

갓민상님과 mmm님의 도움을 받아 풀이를 완성했다.

https://github.com/tony9402/FastCampus_Solution/blob/main/SET_5/06/Main.java

 

 

2021.09.14 - [알고리즘 문제 풀이/백준] - 백준 22868 산책 (small) Kotlin (bfs)

산책 small 문제를 풀고 large로 넘어와, 기존 small 코드를 다익스트라버전으로 리팩토링하여 제출하였다.

50퍼 정도에서 시간 초과가 떴고, 통과하기 위해선, 사전 순으로 가장 앞선 최단 경로를 빠르게 찾는 방법이 필요했다.

갓민상님의 풀이를 참고하여 가장 앞선 최단 경로를 빠르게 찾을 수 있었고, 풀이는 다음과 같다.

//다익스트라 : 한 정점에서 모든 정점을 최단 거리로 방문하는 알고리즘

1. 다익스트라로 S에서 모든 정점에 대한 최단 거리를 구하여 distS에 저장한다.

2. 다익스트라로 E에서 모든 정점에 대한 최단 거리를 구하여 distE에 저장한다.

3. distS[E](S에서 E까지의 최단 거리)를 최종 리턴 값 answer에 더한다.

4. distS,distE를 이용해 S->E까지 최단 거리로 이동하면서 이동한 경로들 중 사전 순으로 앞선 값을 찾는다.

4.1 S에서 시작하여 S와 연결된 다음 노드를 N이라 할 때, dist[S]+N노드로 가는 거리(증가치) + distE[N] == distS[E]
    라면 해당 노드는 최단 경로에 사용된 노드가 맞다. 

4.2 S에서 시작하여 S와 연결된 또 다른 다음 노드를 M이라 할 때, 4.1의 과정을 반복한 후, N,M을 비교하여 낮은 수가
    사전 순으로 앞선 경로가 된다. 

4.3 N,M중 작은 수가 N이라고 할 때, S를 N으로 갱신해 준다.

4.4 위의 4.1~4.3 과정을 S가 E가 될 때까지 반복하고, 여기서 구한 노드들을 used[]배열에 true로 저장하여 S->E에서 
     사용된 노드들임을 저장한다.

5. used배열에 true로 저장되어 있는(S->E 경로에서 이미 사용한)노드들을 제외하고 다익스트라를 돌린 후, distE[S]값을
   answer에 더해준다. 

 

문제에서 모든 값은 Int 범위를 초과하지 않으므로 answer도 Int형으로 해도 무관하다.

코드

import kotlin.math.*
import java.util.*
val used = BooleanArray(200001)

fun dijkstra(graph: Array<ArrayList<Pair<Int,Int>>>, s : Int) : IntArray{
    val dp = IntArray(graph.size){987654321}
    val pq = PriorityQueue<Pair<Int,Int>>(Comparator{a,b -> when{
        a.second <b.second -> -1
        a.second ==b.second -> 0
        else -> 1
    }})
    pq.add(Pair(s,0))
    dp[s]=0
    while(pq.isNotEmpty()){

        val (cur,curDis) = pq.poll()
        if(dp[cur] != curDis) continue
        for(i in graph[cur].indices){
            val next = graph[cur][i].first
            val nextDis = curDis+graph[cur][i].second
            if(used[next]) continue
            if(dp[next]>nextDis) {
                dp[next] = nextDis
                pq.add(Pair(next, nextDis))
            }
        }
    }

    return dp
}

fun eraseEdge(distS : IntArray, distE : IntArray, graph : Array<ArrayList<Pair<Int,Int>>>,start : Int, e : Int){

    var pre =start
    var s = start
    while(s!=e){
        var minNode = 987654321

        for (i in graph[s].indices) {
            val (next,nextDis) = graph[s][i]
            if (next == pre) continue
            if(distS[s]+nextDis+distE[next]==distS[e]){
                minNode = min(minNode,next)
            }
        }
        if(s!=e){
            used[minNode]=true
        }
        pre =s
        s= minNode
    }


}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m) = List(2){Integer.parseInt(tk.nextToken())}
    val graph = Array<ArrayList<Pair<Int,Int>>>(n+1){ArrayList()}
    for(i in 0 until m){
        tk = StringTokenizer(br.readLine())
        val (from,to, dis) = List(3){Integer.parseInt(tk.nextToken())}
        graph[from].add(Pair(to,dis))
        graph[to].add(Pair(from,dis))
    }
    tk = StringTokenizer(br.readLine())
    val (s,e) = List(2){Integer.parseInt(tk.nextToken())}
    val distS = dijkstra(graph,s)
    var distE = dijkstra(graph,e)
    var answer : Long =distS[e].toLong()
    eraseEdge(distS,distE,graph,s,e)

    distE = dijkstra(graph,e)
    answer+=distE[s]
    write("$answer")
    close()
}