Daily LeetCode Challenge - 2359. Find Closest Node to Given Two Nodes

Problem From.

https://leetcode.com/problems/find-closest-node-to-given-two-nodes/

오늘 문제는 방향성이 있는 graph 가 주어지고, node1 과 node2 가 주어졌을 때,
주어진 node1 과 node2 으로부터 공통적으로 접근할 수 있으며, 각각의 노드로부터의 거리가 최소로 될 수 있는 노드의 index 를 구하는 문제였다.

이 문제는 BFS 로 풀 수 있으며, 먼저 node1 과 node2 를 각각 BFS 를 활용하여 갈 수 있는 모든 노드의 각각의 거리를 구한다음, 그 거리 리스트를 비교하면서 공통된 노드의 최소 거리를 가진 노드의 index 를 반환하였다.

아래 답의 시간 복잡도는 O(N) 이 된다.

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        
        val distance1 = BFS(edges, node1)
        val distance2 = BFS(edges, node2)
        
        var index = -1
        var min = Integer.MAX_VALUE
        
        for(i in 0 until edges.size) {
            if(distance1[i] == -1 || distance2[i] == -1) continue
            val max = Math.max(distance1[i], distance2[i])
            if(max < min) {
                min = max
                index = i
            }
        }
        
        return index
    }
    
    private fun BFS(edges: IntArray, node: Int) : IntArray {
        val path = IntArray(edges.size) { -1 }
        val queue : Queue<Int> = LinkedList()
        val hashSet = hashSetOf<Int>()
        
        var distance = 0
        queue.add(node)
        hashSet.add(node)
        while(queue.isNotEmpty()) {
            for(i in 0 until queue.size) {
                val curr = queue.poll()
                path[curr] = distance
                val next = edges[curr]
                if(next == -1 || hashSet.contains(next)) continue
                hashSet.add(next)
                queue.add(next)
            }
            distance += 1
        }
        return path
    }
}