Find Closest Node to Given Two Nodes

인덱스를 기준으로 단방향 그래프들의 간선을 의미하는 정수 벡터 edges와

특정 인덱스 두 개 node1과 node2를 받는다.

문제는 두 노드들이 모두 도달할 수 있는 노드들 중 node1과 node2에서 더 먼 거리를 기준으로

가장 작은 거리를 가지는 노드의 인덱스를 반환하는 것이다.

만약 두 노드들이 동일하게 접근할 수 있는 노드가 존재하지 않을 경우 -1을 반환하며

동일한 거리가 있을 경우 더 작은 인덱스를 반환

Return the index of the node that can be reached from both node1 and node2, such that the maximum between the distance from node1 to that node, and from node2 to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.

문제를 푸는 것보다 영어를 해석하는게 더 어려웠던 것 같다.

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        
        int length = edges.size();
        vector<int> distances[2];

        distances[0].resize(length, -1);
        distances[1].resize(length, -1);

        distances[0][node1] = 0;
        SearchDFS(node1, edges, distances[0]);

        distances[1][node2] = 0;
        SearchDFS(node2, edges, distances[1]);

        int result{-1};
        int minDistance{numeric_limits<int>::max()};

        for (int i = 0; i < length; i++)
        {
            if (distances[0][i] == -1 || distances[1][i] == -1)
            {
                continue;
            }

            int maxDistance{std::max(distances[0][i], distances[1][i])};
            if (maxDistance < minDistance)
            {
                minDistance = maxDistance;
                result = i;
            }
            
        }

        return result;
    }

private:
    void SearchDFS(int &node, vector<int>& edges, vector<int> &distance)
    {
        if (edges[node] == -1)
        {
            return;
        }

        if (distance[edges[node]] == -1)
        {
            distance[edges[node]] = distance[node] + 1;
            SearchDFS(edges[node], edges, distance);
        }

        return;
    }
};