[C++] 프로그래머스 네트워크

프로그래머스 '네트워크' 문제 보러가기

BFS를 이용한 문제이다.

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

using namespace std;

int visited[205];
queue<int> q;

void bfs(int n,int num, vector<vector<int>> coms){
    visited[num] = 1;
    q.push(num);
    while(!q.empty()){
        int e = q.front();
        q.pop();
        for(int i=0;i<n;i++){
            if(coms[e][i]==1 && visited[i]!=1){
                q.push(i);
                visited[i]=1;
            }
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0;i<n;i++){
        if(visited[i]!=1){
            bfs(n,i, computers);
            answer++;
        }
    }
    
    return answer;
}

모든 정점을 방문할 때까지 BFS를 실행하면서, BFS가 실행되는 횟수를 통해 연결된 네트워크의 개수를 헤아린다.