leetcode Problem - 2359 풀이

LeetCode 2359. Find Closest Node to Given Two Nodes

문제

문제 링크

N개의 노드를 가지는 방향 그래프가 주어지며, 노드는 0번 부터 N-1번의 번호를 갖는다. 각 노드는 최대 하나의 나가는 엣지를 가진다. 그래프는 edges 배열로 표현 되며, edges[i] = j 는 i번 노드로부터 나가는 엣지는 j번 노드에 연결되어 있다는 뜻이다. edges[i] = -1 이면 나가는 엣지는 없다.

이 때, 두 개의 노드(노드1, 노드2)가 주어질 때, 각 노드로부터 다다를 수 있는 공통의 노드 중에서 다음의 조건을 만족하는 노드를 찾는다. 없으면 -1을 반환한다.

• 노드1 로부터 공통 노드 까지의 거리와 노드2 로부터 공통 노드 까지의 거리 중 큰 값이 가장 최소가 되는 공통 노드

해결

시작점이 두 개이므로, 두 개의 1차원 배열을 만들어서 두 개의 출발 노드로부터 도달하는 노드들 까지의 거리를 기록한다. 사이클이 존재하므로 이미 거리가 기록된 노드에 다시 방문한다면 즉시 기록을 중지한다.

두 번의 반복이후에는 두 개의 배열의 i 인덱스에는 각각의 노드로부터 노드 i 까지의 거리가 기록되어 있을 것이다.

마지막으로 두 개의 배열을 동시에 순환하며, 조건을 만족하는 노드를 찾는다.

코드

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val count1 = Array<Int>(edges.size){ -1 }

        var current = node1
        var distance = 0
        while (count1[current] == -1) {
            count1[current] = distance++
            if (edges[current] != -1) {
                current = edges[current]
            } else {
                break
            }
        }

        val count2 = Array<Int>(edges.size){ -1 }
        current = node2
        distance = 0
        while (count2[current] == -1) {
            count2[current] = distance++
            if (edges[current] != -1) {
                current = edges[current]
            } else {
                break
            }
        }

        var minIndex = -1
        var minValue = Int.MAX_VALUE
        for (i in edges.indices) {
            if (count1[i] != -1 && count2[i] != -1) {
                val value = kotlin.math.max(count1[i], count2[i])
                if (value < minValue) {
                    minIndex = i
                    minValue = value
                }
            }
        }
        
        return minIndex
    }
}