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

 

문제

프로그래머스

 

이 문제는 간선으로 이어진 그래프(네트워크)의 갯수를 구하는 문제이다.

---

풀이

BFS를 이용하여 각 노드들을 탐색하고 간선으로 이어지지 않은 정점의 갯수를 구하는 방법으로 풀이했다.

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

using namespace std;

bool visited[200] = {false,};

void BFS(vector<vector<int>> computers , int startNode){
    
    queue<int> q;
    
    q.push(startNode);
    visited[startNode] = true;
    
    while(!q.empty()){
        int node = q.front();
        
        q.pop();
        
        for(int i = 0 ; i< computers[node].size(); i++){
            if(!visited[i] && computers[node][i] == 1){
                visited[i] = true;
                q.push(i);
            }
        }
        
    }
}

int solution(int n, vector<vector<int>> computers) {

    int answer = 0;
    for(int i = 0; i< n; i++){
        if(!visited[i]){
            BFS(computers , i);
            answer++;
       }
    }
    

    return answer;
}