23.01.25 Today’s Leetcode

2359. Find Closest Node to Given Two Nodes (medium)

55/71 passed testcases 문제 이해를 이상하게 한 듯 하다. 믈룽

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        tree = defaultdict(list)
        for index, edge in enumerate(edges):
            tree[index].append(edge)
            # tree[edge].append(index)

        n = len(edges)
        def get_dist(node_index):
            count = 0
            queue, temp = [node_index], []
            dist_from = [-1] * n
            while queue:
                target = queue.pop()
                dist_from[target] = count
                for node in tree[target]:
                    if dist_from[node] == -1:
                        temp.append(node)
                if len(queue) == 0:
                    queue = temp[:]
                    temp = []
                    count += 1
            return dist_from
        
        dist_from1 = get_dist(node1)
        dist_from2 = get_dist(node2)

        print(dist_from1)
        print(dist_from2)

        if dist_from1[node2] != -1 and dist_from2[node1] != -1:
            if dist_from1[node2] < dist_from2[node1]: return node2
            elif dist_from1[node2] > dist_from2[node1]: return node1
            else: return min(node1, node2)
        elif dist_from1[node2] != -1:
            return node2
        elif dist_from2[node1] != -1:
            return node1
    
        temp = -10**9
        res = -1
        for i in range(n):
            a, b = dist_from1[i], dist_from2[i]
            if a == -1 or b == -1:
                continue
            if a - b > temp:
                res = i
                temp = a - b
            
        return res

class Solution:
    def dfs(self, node, edges):
        cur, dist = node, 0
        ans = [-1]*len(edges)
        
        while cur != -1 and ans[cur] == -1:
            ans[cur] = dist
            dist += 1
            cur = edges[cur]
            
        return ans
    
    def closestMeetingNode(self, edges, node1, node2):
        dist1 = self.dfs(node1, edges)
        dist2 = self.dfs(node2, edges)
        
        min_node, min_dist = -1, float("inf")
        
        # min_dist 를 구하는 것 까지는 비슷했으나.. 
        for i in range(len(edges)): 
            if dist1[i] == -1 or dist2[i] == -1:
                continue
            # 이 부분에서 조금 달랐다. 
            if min_dist > max(dist1[i], dist2[i]):
                min_node = i
                min_dist = max(dist1[i], dist2[i])
                
        return min_node