2023.01.25 Today's Challenge

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

Find Closest Node to Given Two Nodes - LeetCode

DFS를 활용해서 푸는 문제

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        inf = float('inf')
        n = len(edges)

        dist_n1 = [inf for _ in range(n)]
        dist_n2 = [inf for _ in range(n)]

        def dfs(node, di, d):
            if d[node] > di:
                d[node] = di
                if edges[node] != -1:
                    dfs(edges[node], di+1, d)
        
        dfs(node1, 0, dist_n1)
        dfs(node2, 0, dist_n2)

        for i in range(n):
            dist_n1[i] = max(dist_n1[i], dist_n2[i])
        
        ans = dist_n1.index(min(dist_n1))

        return ans if dist_n1[ans] != inf else -1