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

#include <string>
#include <vector>
#include <queue>
#include <iostream>
 
using namespace std;
 
bool check[201];
vector<int> vec[201];
 
void bfs(int x) {
    queue<int> q;
    q.push(x);
    
    while(!q.empty()) {
        int nx = q.front();
        q.pop();
        
        for(int i=0; i<vec[nx].size(); i++) {
            if(check[vec[nx][i]]) {continue;}
            check[vec[nx][i]] = true;
            q.push(vec[nx][i]);
        }
    }
}
 
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int cpu_size = computers.size();
    
    for(int i=0; i<cpu_size; i++) {
        for(int j=0; j<cpu_size; j++) {
            if(j == i) {continue;}
            if(computers[i][j] == 1) {
                vec[i].push_back(j);
            }
        }
    }
    
    for(int i=0; i<cpu_size; i++) {
        if(check[i]) {continue;}
        check[i] = true;
        answer++;
        bfs(i);
    }
    
    return answer;
}

풀이방법으로 두가지 알고리즘을 사용할 수 있는 문제이다.

 

1. bfs

2. union-find

 

위의 코드에선 bfs를 사용했다. 

 

1. 2차원 벡터인 computers 벡터를 이용해 노드 연결2.  0 번째 컴퓨터부터  bfs를 실행 연결된 컴퓨터는 check 배열을 이용해 true로 바꿔준다.3. check[컴퓨터번호] == true 라면 bfs 생략 false 일 경우 bfs를 실행하며 answer 값을 1씩 더해줌