[C++] 네트워크

나는 이런 벡터를 생성하고 값을 넣어줬다.

    vector<pair<bool,vector<int>>> network;
    for(int i = 0; i < computers.size(); i++) {
        vector<int> net;
        for(int j = 0; j < computers.size(); j++) {
           if(computers[i][j] == 1) {   //has edge
               net.push_back(j);
           } 
        }
        network.push_back(make_pair(false,net));
        net.clear();
    }

3, [[1,1,0],[1,1,0],[0,0,1]], 2 (예제) 의 경우

bool	vector<int>
false	0, 1
false	0, 1
false	2

bool값은 이 노드가 네트워크로 카운트되었는가를 저장할 것이고,
vector<int>는 이 노드에 연결된 모든 노드 벡터이다.
나는 재귀함수로 접근해서 문제를 풀었다.

void checkNetwork(int node, vector<pair<bool,vector<int>>>& network) { //연결된 모든 노드의 값을 true로 바꾸는 함수    
    for(int ele : network[node].second) {   //1
        if(ele == node || network[ele].first == true) {
            continue;
        }  
        cout << ele << endl;
        network[ele].first = true;
        checkNetwork(ele, network);
    }
}

재귀 함수 자체는 node index를 넣어주면, 거기 second에 적혀있던 모든 노드를 재귀로 검사하고, 얘 네트워크에 속해있어~ 하고 true값으로 바꿔주는 함수이다.
따라서 이 재귀 함수를 모든 node에 따라 실행해주면 된다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void checkNetwork(int node, vector<pair<bool,vector<int>>>& network) { //연결된 모든 노드의 값을 true로 바꾸는 함수    
    for(int ele : network[node].second) {   //1
        if(ele == node || network[ele].first == true) {
            continue;
        }  
        cout << ele << endl;
        network[ele].first = true;
        checkNetwork(ele, network);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<pair<bool,vector<int>>> network;
    for(int i = 0; i < computers.size(); i++) {
        vector<int> net;
        for(int j = 0; j < computers.size(); j++) {
           if(computers[i][j] == 1) {   //has edge
               net.push_back(j);
           } 
        }
        network.push_back(make_pair(false,net));
        net.clear();
    }
    
    for(int i = 0; i < n; i++) {
        if(network[i].first == false) { //새로운 네트워크
            answer++;
            cout << "New Network Detected. Current Network : " << answer << endl;
            cout << "Start From Node " << i << endl;
            checkNetwork(i,network);    //연결된 모든 노드의 값을 true로 바꾸는 함수
            cout << "Network End." << endl;
        }
    }

    
    
    return answer;
}

출력값을 대조해보면서 코드를 보면 이해가 잘 될 것이다!

* 여담
나는 이게 "상호 간 네트워크" 니까 양방향일거라고(그래프가 대칭일것이다) 지레짐작하고 코드를 짰는데, 그러면 안된다.
테스트 3에 해당하는 값을 꼭꼭 돌려보길!

++++ 복습 후 다시 풀어봄!
내가 풀었던 방법은 이차원배열로 값이 주어진 걸 굳이 또 연결리스트 형태로 바꾼 필요없는 과정이 있었다.
이 문제를 재귀함수를 통한 DFS 개념으로 풀었던데, 이 문제는 BFS, DFS 모두가능한 유형이기도 해서 BFS로 풀어봤다.

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

#include <iostream>

using namespace std;

void check_node_network(int node, int n, vector<vector<int>> computers, vector<bool> &network, queue<int> &network_q) {
        for(int j = 0; j < n; j++) {
        if(j == node) continue;
        if(computers[node][j] == 1 && network[j] == false) {   //connected
            cout << "<-" << j;
            network[j] = true;
            network_q.push(j);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> network(n,false);  // network count vector
    queue<int> network_q;   //for BFS
    
    
    for(int i = 0; i < n; i++) {
        if(network[i]) continue;    //already counted computer
        else {  //new network
            network[i] = true;
            answer++;
            cout << "New Network : " << answer << endl;
            cout << i;
        }
        check_node_network(i,n,computers,network,network_q);
        
        while(!network_q.empty()) {
            int node = network_q.front();
            network_q.pop();
            check_node_network(node,n,computers,network,network_q);
        }
        cout << endl;
     }
    return answer;
}

함수는 그냥 해당 노드의 유효 네트워크 연결 컴퓨터를 검사하는 함수!
Queue를 이용해서 BFS로!

아예 다른 방법으로 푼 건데 정말 빨리 풀었다. 성장했나바 (^^)