[백준 9379번] [Kotlin] 미확인 도착지

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

9370번: 미확인 도착지

 

난이도 : 골드 2
태그 : 데이크스트라, 그래프 이론

 

 

1. 설명

다익스트라를 응용한 문제입니다.

 

S에서 시작하여, G - H 혹은 H - G 구간을 거쳐, t1, t2, t3, 총 3개의 목적지 후보로 갈 수 있다 가정해보겠습니다.

이 때, 시작점인 S와 목적지인 T1의 최단거리가

S - G - H - T1 혹은 S - H - G - T1 과 같을 때, T1은 가능한 목적지 경로입니다.

S - G - H - T2, S - H - G - T2 모두 S - T2 와 같지 않으면, 이는 불가능한 목적지 경로입니다.

 

즉, 모든 목적지 T에 대해

다익스트라를 사용하여

(S-G 최단경로) + (G-H 최단경로) + (H-T 최단경로) 또는

(S-H 최단경로) + (H-G 최단경로) + (G-T 최단경로)가

(S-T 최단경로) 와 같은지 확인하면 됩니다.

 

 

2. 소스코드

 

      

      

      

    
    

      <kotlin />
    
import java.util.*
import kotlin.collections.ArrayList

class Node(val index: Int, val cost: Int) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return (this.cost - other.cost)
    }
}

var n = 0
var m = 0
var t = 0
var s = 0
var g = 0
var h = 0

lateinit var graph: Array<ArrayList<Node>>
lateinit var candidate: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {

    val sb = StringBuilder()

    repeat(readLine().toInt()) {
        var st = StringTokenizer(readLine())
        n = st.nextToken().toInt()
        m = st.nextToken().toInt()
        t = st.nextToken().toInt()

        // s - 예술가 출발지, g - h 구간
        st = StringTokenizer(readLine())
        s = st.nextToken().toInt()
        g = st.nextToken().toInt()
        h = st.nextToken().toInt()


        graph = Array(n + 1) { ArrayList<Node>() }
        repeat(m) {
            st = StringTokenizer(readLine())
            val (a, b, d) = Array(3) { st.nextToken().toInt() }
            graph[a].add(Node(b, d))
            graph[b].add(Node(a, d))
        }

        // 목적지 후보들
        candidate = Array(t) { readLine().toInt() }.sortedArray()

        val goals = ArrayList<Int>()

        // 다익스트라
        candidate.forEach { target ->
            val shortestLength = dijkstra(s, target)
            val path1 = dijkstra(s, g) + dijkstra(g, h) + dijkstra(h, target)
            val path2 = dijkstra(s, h) + dijkstra(h, g) + dijkstra(g, target)

            if (shortestLength == path1 || shortestLength == path2) {
                goals.add(target)
            }
        }

        goals.sorted().forEach {
            sb.append(it).append(" ")
        }
        sb.append("\n")
    }

    print(sb)
}


fun dijkstra(start: Int, end: Int): Int {
    val dist = Array(n + 1) { Int.MAX_VALUE }
    dist[start] = 0

    val pq = PriorityQueue<Node>()
    pq.offer(Node(start, 0))

    while (pq.isNotEmpty()) {
        val nowNode = pq.poll()
        if (nowNode.cost > dist[nowNode.index]) continue

        graph[nowNode.index].forEach { nextNode ->
            if (dist[nextNode.index] > nowNode.cost + nextNode.cost) {
                dist[nextNode.index] = nowNode.cost + nextNode.cost
                pq.offer(Node(nextNode.index, nowNode.cost + nextNode.cost))
            }
        }
    }

    return dist[end]
}

 

 

 

3. 후기

다익스트라를 응용하여 풀 수 있었던 문제였습니다.

평소 우선순위 큐를 사용한 다익스트라를 잘 해보지 않아 좀 어색했지만,

이제 조금 익숙해져가네요.