Shortest Path with Alternating Colors

그래프의 노드 개수 n과 빨간 선 redEdges, 파란 선 blueEdges 벡터들을 받는다

빨간, 파란 선 벡터에는 시작점과 도착점이 벡터로 들어있으며,

문제는 인덱스를 기준으로 0번째부터 n - 1번째까지 몇 번만에 갈 수 있는지 구하는 것인데,

이전에 빨간 선을 통해 이동했으면 다음 번 이동은 무조건 파란 선을 통해 이동해야하고,

파란 선을 통해 이동했으면 반대로 무조건 빨간 선을 통해 이동해야 된다.

접근 할 수 없는 인덱스 노드의 경우는 -1을 반환하면 된다.

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {

        vector<list<pair<int, int>>> graph(n);

        for (auto& edge : redEdges)
        {
            graph[edge[0]].push_back({RED, edge[1]});
        }

        for (auto& edge : blueEdges)
        {
            graph[edge[0]].push_back({BLUE, edge[1]});
        }
        
        vector<int> result(n, -1);

        queue<pair<int, int>> waitings{};
        waitings.push({NONE, 0});

        int counter{0};
        while (waitings.empty() == false)
        {
            int length = waitings.size();
            for (int i = 0; i < length; ++i)
            {
                auto position = waitings.front();
                waitings.pop();

                if (result[position.second] == -1)
                {
                    result[position.second] = counter;
                }

                for (auto it = graph[position.second].begin(); it != graph[position.second].end();)
                {
                    if (position.first == it->first)
                    {
                        ++it;
                    }
                    else
                    {
                        waitings.push(*it);
                        it = graph[position.second].erase(it);
                    }
                }
            }

            ++counter;
        }

        return result;
    }

private:
    const int NONE = 0;
    const int RED = 1;
    const int BLUE = 2;
};