DFS/BFS 네트워크

 

 

<코드 구현>

 

 모든 정점들이 방문(TRUE) 상태가 될 때 까지 DFS를 만들고, DFS가 만들어질 때 마다 NEWTORK의 수를 증가 시키면 된다.

#include <string>
#include <vector>
#include <stack>

#define MAX 200
using namespace std;


vector<bool> visited;

int dfs(int n, vector<vector<int>> computers) ;


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    visited = vector<bool>(n,false);
    answer = dfs(n,computers);

    return answer;
}

int dfs(int n, vector<vector<int>> computers) {
    int networks = 0;
    int idx=0;
    stack<int> s;
    bool flag;
    

    
    for(int i=0; i<n; ++i) {
        if(visited[i]) continue;
        visited[i] = true;
        s.push(i);
        
        while(!s.empty()) {
        
           idx = s.top();
           flag = false;

            for(int j=0; j<n; ++j){
                if(!computers[idx][j] || (j==idx) || visited[j]) continue;
                s.push(j);
                visited[j] = true;
                flag = true;
            }
            if(!flag) s.pop();
        }
        networks++;
    }
    
    return networks;
    
}