[백준 17270번] [Kotlin] 연예인은 힘들어

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

17270번: 연예인은 힘들어

 

난이도 : 골드 3
태그 : 구현, 그래프 이론, 데이크스트라, 플로이드–워셜

 

 

1. 설명

다익스트라 혹은 플로이드 워셜을 응용해 풀 수 있는 문제입니다.

 

계속 틀렸습니다를 받아서 질문게시판을 들여다봤는데,

아니나 다를까 지문이 불친절하다는 의견이 잔뜩 있었습니다...

질문게시판들을 둘러보며 지문을 몇 번이고 다시 읽어봤는데,

 

 

해당 조건을 하나씩 적용하면서 풀어야 하는 문제입니다.

 

지헌이의 출발 위치나 성하의 출발 위치가 아니면서,

지헌이가 성하보다 빨리 도착하는 위치 중 최단거리를 찾으라는 것이 아닌,

 

지헌이와 성하의 출발 위치가 아니면서,

최단경로로 갈 수 있는 노드들이 후보 노드들이고, 이 중에서 지헌이가 늦게 도착하는 경우는 제외하는 것입니다.

 

 

J는 지헌이의 시작 위치, S는 성하의 시작 위치입니다

 

위 노드들 중 최단 경로를 가진 노드는 1, 3번 노드입니다.

1번 노드의 경우,

지헌이는 4의 비용, 성하는 3의 비용으로 총 7의 비용을 갖습니다. 하지만 지헌이가 더 늦게 도착하므로 약속 장소가 될 수 없습니다.

3번 노드의 경우,

지헌이는 6의 비용, 성하는 1의 비용으로 총 7의 비용을 갖습니다. 하지만 이번에도 지헌이가 더 늦게 도착하므로 유효한 장소가 아닙니다.

 

그럼 그 다음 최단경로이면서 지헌이가 더 빨리 도착하는 4번 노드(비용 8)가 약속 노드가 되는 것이 아닌, 

그냥 조건을 만족하는 약속 장소가 없다(-1 출력)가 정답입니다...

 

때문에 조건을 하나씩 적용하면서 풀어야 한다는 것이고요.

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
import java.util.StringTokenizer

const val INF = 987654321

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }

    val table = Array(n + 1) { Array(n + 1) { INF } }

    repeat(n + 1) {
        table[it][it] = 0
    }

    repeat(m) {
        val st = StringTokenizer(readLine())
        val (v1, v2, cost) = Triple(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt())
        table[v1][v2] = minOf(table[v1][v2], cost)
        table[v2][v1] = minOf(table[v2][v1], cost)
    }

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (table[i][j] > table[i][k] + table[k][j]) table[i][j] = table[i][k] + table[k][j]
            }
        }
    }

    val (pointJ, pointS) = readLine().split(" ").map { it.toInt() }
    
    var minDistance = INF

    for (destination in 1..n) {
        if (destination == pointJ || destination == pointS) continue
        if (table[pointJ][destination] == INF || table[pointS][destination] == INF) continue
        if (table[pointJ][destination] + table[pointS][destination] > minDistance) continue
        minDistance = table[pointJ][destination] + table[pointS][destination]
    }

    var minDistanceOfJihyeon = INF
    var answerIdx = -1

    for (destination in 1..n) {
        if (destination == pointJ || destination == pointS) continue
        if (table[pointJ][destination] + table[pointS][destination] != minDistance) continue
        if (table[pointJ][destination] > table[pointS][destination]) continue
        if (table[pointJ][destination] > minDistanceOfJihyeon) continue

        minDistanceOfJihyeon = table[pointJ][destination]
        answerIdx = destination
    }

    println(answerIdx)
}

 

저는 플로이드-와샬 알고리즘으로 모든 노드쌍의 최단 경로를 구해준 뒤,

해당 경로로부터 지헌이까지의 최단경로, 성하까지의 최단경로를 찾고,

조건에 만족하는 노드를 찾아줬습니다.

 

 

 

3. 후기

접근 방법(플로이드 와셜/다익스트라 응용 방법)은 빠르게 떠올릴 수 있었으나

조건이 다소 까다로워 헤매였던 문제였습니다.