(DFS/BFS)네트워크

풀이

• 인접행렬 vs 인접리스트
• 인접행렬은 노드간 링크가 조밀할 경우 사용하는게 효율적 -> 이문제에서는 인접리스트를 이용해서 각각의 노드별로 연결된 것들을 탐색하는 방법 사용
• dfs
• dfs에서 연결된 컴포넌트와 연결되지 않은 컴포넌트의 개수를 모두 구해야함

코드

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

using namespace std;
vector<int> adj[200];
int visited[200];
int answer; //하나의 노드와 연결된 노드들 탐색
int conn; //연결된 컴포넌트 내부의 개수 

void dfs(int i,int n){
    conn++;
    visited[i]=1;
    for(auto ele : adj[i]){
        if(adj[ele].size()>0 && !visited[ele]){
            dfs(ele,n);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                continue;
            }
            if(computers[i][j]==1){
                adj[i].push_back(j);           
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     cout << i <<":";
    //     for(auto ele : adj[i]){
    //         cout << ele <<' ';
    //     }
    //     cout << '\n';
    // }

    for(int i=0;i<n;i++){
        if(adj[i].size()>0 && !visited[i]){
            answer++;
            dfs(i,n);
        }
    }
    int result=answer+n-conn; //하나에 연결된 노드를 컴포넌트로 보고 연결되지 않은 네트워크의 개수는 전체 컴퓨터수에서 뺀다

    return result;
}