[Algorithm] Programmers :: 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162?language=cpp 

코딩테스트 연습 - 네트워크

vector<vector<int>> graph;
bool visitedMap[200];
 
void DFS(int n)
{
    if (visitedMap[n]) return;
    visitedMap[n] = true;
 
    for (int i = 0; i < graph[n].size(); i++) // n과 연결된 노드들 탐색.
    {
        int nextNode = graph[n][i];
        DFS(nextNode);
    }
}
 
int solution(int n, vector<vector<int>> computers) 
{
    int answer = 0;
    graph.resize(n);
 
    for (int i = 0; i < computers.size(); i++)
    {
        for (int j = 0; j < computers[0].size(); j++)
        {
            if (i == j) continue; // 자기자신은 제외
            if (computers[i][j] == 1) // i랑 j가 연결되어있으면,
            {
                graph[i].push_back(j);
            }
        }
    }
 
    for (int i = 0; i < computers.size(); i++)
    {
        if (visitedMap[i]) continue;
        DFS(i);
        answer++;
    }
 
    return answer;
}

각 노드들의 덩어리개수를 구하는 문제다.

먼저 그래프를 인접리스트로 모델링 한 후에, 방문안된 노드들에 한해서 DFS를 돌리고 answer++을 한다.

DFS를 진행한 노드들은 앞서 탐색이 안된 노드들이기 때문에 새로운 덩어리의 출발로 인지한다.