[Programmers/C++] 네트워크

시간 복잡도

• BFS를 연결리스트를 이용하여 구현하면 시간 복잡도는 $O(ElogV)$ 입니다.

문제 접근법

• 연결되어 있는 네트워크 그룹의 개수를 구하는 문제입니다.
• BFS를 이용하면 탐색 과정에서 방문한 모든 노드들은 하나의 네트워크에 속하게 됩니다,
• 방문하지 않은 모든 노드들을 대상으로 BFS를 수행하며 정답을 카운트합니다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

static vector<vector<int>> G;
static vector<int> visited;

void BFS(int node)
{
    queue<int> q;
    q.push(node);
    visited[node]=true;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        for(int next : G[now])
        {
            if(!visited[next])
            {
                visited[next]=true;
                q.push(next);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    G.resize(n);
    visited.resize(n, false);
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i==j)
                continue;
            
            if(computers[i][j])
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    
    for(int i=0; i<n; i++)
    {
        if(!visited[i])
        {
            BFS(i);
            answer++;
        }
    }
    
    
    return answer;
}