[Leetcode 2359] Find Closest Node to Given Two Nodes

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

1) 내 첫 코드

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:

        pos = -1 
        answer = 1e9         
        n = len(edges)
        graph = [[] for _ in range(n)]
        distance = [[-1]*n for _ in range(2)]
        visited = set()

        for i in range(n):
            graph[i].append(edges[i])


        def dfs(start, curr, dist, nodeType):
            visited.add(curr)
            distance[nodeType][curr] = dist
            nextNode = graph[curr][0]

            if nextNode != -1 and nextNode not in visited:
                dfs(start, nextNode, dist+1, nodeType)
            else:
                return 

        dist = 0 
        visited.clear() 
        dfs(node1, node1, dist, 0)
        visited.clear() 
        dfs(node2, node2, dist, 1)

        for j in range(n):
            arr = [] 
            for i in range(2):
                if distance[i][j] != -1:
                  arr.append(distance[i][j])

            if (len(arr) == 1 and node1 == node2) or len(arr) == 2:
                if answer > max(arr):
                    answer = max(arr)
                    pos = j

        return pos 

2) 참고 코드

class Solution:

    def dfs(self, node, edges, dist):
        distance = 0 

        while node != -1 and dist[node] == -1:
            dist[node] = distance
            distance += 1 
            node = edges[node]


    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        
        result = -1
        maxVal = 1e9
        n = len(edges)

        dist1 = [-1]*n
        dist2 = [-1]*n

        self.dfs(node1, edges, dist1)
        self.dfs(node2, edges, dist2)

        for i in range(n):
            if min(dist1[i], dist2[i]) >= 0 and max(dist1[i], dist2[i]) < maxVal:
                maxVal = max(dist1[i], dist2[i])
                result = i

        return result 

2) 해설

• DFS를 while문을 통해서도 나타낼 수 있다
• 메모리 사용에 주의해야 한다
  -> 노드가 10만개이므로, O(N)까지만 허용될 수 있다