Daily LeetCode Challenge - 2492. Minimum Score of a Path Between Two Cities

Problem From.

https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/

오늘 문제는 1 부터 n 으로 갈때 각 경로를 통과해서 간다고 가정하였을때, 통과하는 경로 중에서 가장 비용이 적게드는 경로의 비용을 반환하는 문제였다.

이 문제의 핵심은 얼마나 많은 도시를 통과하느냐가 아니라, 가장 비용이 적은 구간을 통과해서 목적지에 도달 할 수 있는지가 핵심이었다. 그 풀이를 구현하기 위해 Union Find 알고리즘을 사용하였다.

경로 압축과 마찬가지고 1 에서 출발해서 목적지인 n 까지 도달할 수 있는 경로를 모두 찾아 압축해나가면서, 압축 될때마다 가장 비용이 적게 드는 경로의 값으로 교체 해주는 식으로 구현하였다.

class Solution {
    
    fun minScore(n: Int, roads: Array<IntArray>): Int {
        
        val route = IntArray(n + 1) { 0 }
        val answer = IntArray(n + 1) { Integer.MAX_VALUE }
        
        for(i in 0..n) {
            route[i] = i
        }
        
        for(i in 0 until roads.size) {
            val start = find(roads[i][0], route)
            val end = find(roads[i][1], route)
            route[start] = route[end]
            answer[start] = Math.min(roads[i][2], Math.min(answer[start], answer[end]))
            answer[end] = Math.min(roads[i][2], Math.min(answer[start], answer[end]))
        }
        
        return answer[find(1, route)]
    }
    
    private fun find(i: Int, route: IntArray) : Int {
        return if(route[i] == i) i else find(route[i], route)
    }

}