[Level_3] 네트워크 (C++)

 

위의 그림은 [[1,1,0],[1,1,0],[0,0,1]] 를 도형화 시켜놓은것이다. 

즉, 이차원 벡터값을 받아와서 현재 노드를 가리키는 인덱스에서 다른 노드를 가리키는 인덱스의 배열값이 1인곳을 방문 처리를 해주면서 dfs 를 돌리면 된다.  

#include <string>
#include <vector>

using namespace std;
bool check[200]; 
int n1; 
void dfs (vector<vector<int>> &v, int node_idx){
    for(int i=0; i<n1; i++){
        if(v[node_idx][i]==1&&check[i]==0){
            check[i]=1; 
            dfs(v,i); 
        }
    }    
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    n1=n; 
    for(int i=0; i<n; i++){
        if(check[i]==0){
            answer++; 
            dfs(computers,i);             
        }
    }
    return answer;
}

코딩테스트 연습 - 네트워크