[Graphs-DFS][Medium] 1466. Reorder Routes to Make All Paths Lead to the City Zero

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. n개의 도시수가 있고, 각 도시 노드의 연결 데이터가 주어진다. 

 이때 어떤 도시에서든, 0 도시에 도달 할 수 있도록, 변경해야 하는 경로의 최소 수를 구하라.

 

위 그림처럼 노드간 1개의 경로가 있고 연결 데이터는 그 순서가 방향을 의미한다.  

 

 

Solution. 

 우선 각 노드는 문제에서 모두 연결되어 있다. 

 따라서 0 노드에서 방향이 없다고 가정하면, 노드 각 방향 어디든 도달 가능해야 한다. 

 이때 도달/탐색 하면서 뒤집힌 방향인 곳만 찾아서 카운팅 하면 될 듯 하다. 

 

 우선 데이터를 노드 index기반으로 변경하여 노드 탐색을 용이케 변경한다. 

 이때 경로의 방향도 함께 기록하여 추후 카운팅의 근거로 삼는다. 

 경로는 일반 탐색이면 될 것이다. 

 

 로직을 코드로 작성해 본다. 

int minReorder(int n, vector<vector<int>>& connections) 
{
    vector<vector<pair<int, bool>>> vLink;	// node id, 방향정보(to) 
    vLink.resize(n);

    // index 노드 기반 접근이 용이토록 데이터 재구성.
    for (int k = 0; k < connections.size(); ++k)
    {
        // 방향 정보도 함께 저장.
        vLink[connections[k][0]].push_back(make_pair(connections[k][1], true));
        vLink[connections[k][1]].push_back(make_pair(connections[k][0], false));
    }

    // BFS 순회. - 0 에서 시작.
    vector<bool> vVisit;
    vVisit.resize(n, false);
    
    queue<pair<int, bool>> qBuff;
    for(int k = 0; k < vLink[0].size(); ++k)
        qBuff.push(make_pair(vLink[0][k].first, vLink[0][k].second));
    vVisit[0] = true;
    
    int retCnt = 0;
    while (!qBuff.empty())
    {
        int id = qBuff.front().first;
        bool toNode = qBuff.front().second;
        qBuff.pop();
        if (vVisit[id])	continue;

        vVisit[id] = true;
        // 0에서 뻗어 나가는 방향이면, 뒤집어야 한다.
        retCnt = toNode ? retCnt + 1 : retCnt;

        for (int k = 0; k < vLink[id].size(); ++k)
            qBuff.push(make_pair(vLink[id][k].first, vLink[id][k].second));
    }
    return retCnt;
}

 

 

결과.