[Graphs-DFS][Medium] 547. Number of Provinces

https://leetcode.com/problems/number-of-provinces/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 vector는 각 노드에 대한 연결 유무를 의미한다. 

 이때 서로 연결되지 않은 노드 덩어리의 수를 구하라. 

 

Solution. 

 그래프의 기본기를 확인하는 좋은 문제라 할 수 있겠다.

 우선 노드 연결의 cycle을 확인하여 그 노드들을 순회 할수 있어야 할 것이고, 

 다음으로, 연결된 노드들이 한 network 안에 있는지 판단할 수 있어야 할 것이다. 

 cycle을 판단하는 것은 직전 문제와 아주 유사하다. 

 다음으로 연결된 노드들이 한 network안에 있는지 판단하려면, 연결된 노드들을 특정 노드로 추렸을때 같은 노드를 향하는지 판단하는 방법이 일반적이다. 여기서는 최소 index를 가진 노드로 할 것이다. 

 

 마지막으로 서로 다른 최소 index 노드들이 총 몇개인지 세면 답이 될 것이다. 

 

 논리대로 코드를 써 본다. 

int findCircle_help(int idx, vector<vector<int>>& isConnected, vector<int>& vCache)
{
    if(vCache[idx] >= 0)
        return vCache[idx];

    int minIdx = idx;

    vector<bool> vVisit;
    vVisit.resize(isConnected.size(), false);
    queue<int> qBuff;
    qBuff.push(idx);

    // BFS로 탐색하며, 최소 index 노드를 찾는다.
    vector<int> vIndices;
    while (!qBuff.empty())
    {
        int curIdx = qBuff.front();
        vIndices.push_back(curIdx);

        qBuff.pop();
        if (vVisit[curIdx])
            continue;

        vVisit[curIdx] = true;
        for (int q = 0; q < isConnected[curIdx].size(); ++q)
        {
            if (curIdx!=q && isConnected[curIdx][q]==1)
            {
                minIdx = min(minIdx, q);
                qBuff.push(q);
            }
        }
    }
    
    // 최적화를 위해 캐싱한다.
    for(int q = 0; q < vIndices.size(); ++q)
        vCache[ vIndices[q] ] = minIdx;

    return minIdx;
}
    
    
int findCircleNum(vector<vector<int>>& isConnected) 
{
    set<int> smallests;
    vector<int> vCache;
    vCache.resize(isConnected.size(), -1);

    // smallest index를 가진 노드로 연결 덩어리를 추린다.
    for (int k = 0; k < isConnected.size(); ++k)
    {
        int idxSmallest = findCircle_help(k, isConnected, vCache);
        // 유일한 수를 체크하기 위해 set에 push 한다.
        if (smallests.find(idxSmallest) == smallests.end())
            smallests.insert(idxSmallest);
    }

    // count how many is that.
    return smallests.size();
}

 

 

적절히 해결 된 듯 하다.