[Kotlin] 백준 22865번 - 가장 먼 곳

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

22865번: 가장 먼 곳

문제 유형

그래프 - 다익스트라, BFS

비슷한 문제: https://programmers.co.kr/learn/courses/30/lessons/72413

풀이

문제에 오타가 좀 있고 지문이 불친절했다.

• 선택 가능한 땅의 위치: 정수 1 ~ n
• 구하고자 하는 것: 가장 가까운 친구(A, B, C) 집까지의 거리 기준 가장 먼 곳의 위치
• 가장 먼 곳이란? - 임의의 위치 X에서 A,B,C까지의 거리 중 가장 가까운 거리, 그리고 그 가까운 거리들 중 가장 먼 거리에 있는 곳
• 각 위치 ~ A,B,C의 거리 중 가장 가까운 거리를 찾아야 하므로 모든 거리는 최단거리 기준으로 생각한다. -> 다익스트라 알고리즘 사용

풀이 과정

1. A ~ (1..n), B ~ (1..n), C ~ (1..n)의 최단거리를 각각 구한다 (다익스트라 3번). -> 모든 위치마다 각 점까지의 최단거리를 구하지 않아도 된다. 그러면 시간복잡도가 O(N^2)이 된다.

 

2. 모든 위치마다 A,B,C까지의 거리 중 가장 짧은 거리와 장소를 계산한다. 

3. 그 중 가장 먼 거리의 장소를 구한다.

for (i in 1..n) {
    var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
    tempMinDist = min(tempMinDist, minDist[2][i])       // 그것과 i ~ C까지의 거리 비교

    // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
    if (maxOfMinDist < tempMinDist) {
        maxOfMinDist = tempMinDist
        answerLand = i
    }
}

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

data class Edge(val from: Int, val to: Int, val dist: Int)

lateinit var graph: Array<MutableList<Edge>> // 인접 리스트

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val (a,b,c) = readLine().split(" ").map(String::toInt)
    val m = readLine().toInt()
    graph = Array(n+1) { mutableListOf<Edge>() }
    val minDist = Array(3){
        IntArray(n+1) { -1 }
    } // a,b,c에서 모든 지점까지의 최단 거리

    repeat(m) {
        val st = StringTokenizer(readLine())
        val land1 = st.nextToken().toInt()
        val land2 = st.nextToken().toInt()
        val dist = st.nextToken().toInt()
        graph[land1].add(Edge(land1, land2, dist)); graph[land2].add(Edge(land2, land1, dist))
    }

    // a,b,c에서 모든 위치까지의 최단거리를 각각 구한다 (다익스트라)
    calculateMinDist(minDist[0], a)
    calculateMinDist(minDist[1], b)
    calculateMinDist(minDist[2], c)

    var maxOfMinDist = 0 // 최단 거리중 가장 먼 거리
    var answerLand = 0   // 그에 연결되는 땅 - 정답
    
    for (i in 1..n) {
        var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
        tempMinDist = min(tempMinDist, minDist[2][i])		// 그것과 i ~ C까지의 거리 비교

        // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
        if (maxOfMinDist < tempMinDist) {
            maxOfMinDist = tempMinDist
            answerLand = i
        }
    }

    println(answerLand)
}

// 다익스트라
fun calculateMinDist(minDist: IntArray, src: Int) {
    val q: Queue<Int> = LinkedList()
    q.offer(src)
    minDist[src] = 0

    while (q.isNotEmpty()) {
        val currentLand = q.poll()

        for (nextEdge in graph[currentLand]) {
            val nextDist = minDist[currentLand] + nextEdge.dist
            // 첫 방문 or 기존 거리보다 짧으면 갱신
            if (minDist[nextEdge.to] == -1 || nextDist < minDist[nextEdge.to]) {
                minDist[nextEdge.to] = nextDist
                q.offer(nextEdge.to)
            }
        }
    }
}