[solved.ac 골드5] 17396_백도어 (다익스트라, 코틀린)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

문제

유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.

최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.

입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.

입력

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.

다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다. 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

출력

첫 번째 줄에 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간을 출력한다. 만약 상대 넥서스까지 갈 수 없으면 -1을 출력한다.

예제

위 그래프의 최단거리는 0-2-3-4 를 지나는 시간인 5(2+2+1) 이지만, 3번 분기점이 상대의 시야에 있기 때문에 0-2-1-4를 지나는 시간인 12(2+4+6)이 최소 시간이 된다.

---

나의 풀이

다익스트라 최단 거리 탐색 알고리즘을 사용해서 풀이할 수 있었다.

2022.08.16 - 코틀린 다익스트라 알고리즘 Kotlin dijkstra algorithm

코틀린 다익스트라 알고리즘 Kotlin dijkstra algorithm

 

import java.util.PriorityQueue

fun solution17396() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val visible = readln().split(" ").map { it.toInt() }.toList()
    val graph = Array(n) { mutableListOf<Pair<Int, Int>>() }
    repeat(m) {
        readln().split(" ").map { it.toInt() }.let { (a, b, c) ->
            if ((a == n - 1 || visible[a] == 0) && (b == n - 1 || visible[b] == 0)) {
                graph[a].add(Pair(b, c))
                graph[b].add(Pair(a, c))
            }
        }
    }

    val distance = Array(n) { Long.MAX_VALUE }
    val q = PriorityQueue<Pair<Int, Long>> { p1, p2 ->
        when {
            p1.second > p2.second -> 1
            p1.second < p2.second -> -1
            else -> 0
        }
    }

    distance[0] = 0
    q.add(Pair(0, 0))

    while (q.isNotEmpty()) {
        val (now, dist) = q.poll()
        if (distance[now] < dist) continue

        for (i in graph[now]) {
            val cost = dist + i.second
            if (distance[i.first] > cost) {
                distance[i.first] = cost
                q.add(Pair(i.first, cost))
            }
        }
    }

    if (distance[n - 1] == Long.MAX_VALUE) println(-1) else println(distance[n - 1])
}

fun main() {
    solution17396()
}

 

다만 주의해야 하는 부분은 시간이 10만 인 것이 최대 30만개 있을 수 있기 때문에 Int 최대 범위를 훌쩍 뛰어넘는다. 그래서 거리를 계산하는 부분은 Long 타입으로 해주어야 한다.

그리고 어차피 마지막 위치를 제외하고 시야에 보이게 되면 (값이 1이면) 갈 수 없는 곳이기 때문에 입력 받을 때 걸러서 저장했다.

채점 결과