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

문제요약

1. 컴퓨터 번호는 0번부터 n-1 까지 매겨지며 n이 주어진다.
2. 각 컴퓨터 간 연결됐는지 여부를 매트릭스로 준다.
3. 여기서 네트워크의 컴포넌트 개수를 구하라.

아이디어

간단한 탐색 문제이다.
dfs를 쓰든 bfs를 쓰든 똑같이 컴포넌트를 구할 수 있지만(닿을 수 있는가?의 개념이기 때문이다)
visited 마킹 겸 어떤 컴포넌트에 속하는지를 저장하고자 consists_of[n]배열을 만들었다.
나는 bfs를 사용하였다.

시간 복잡도 비교

결론은 차이가 없다.

1. DFS
   1) 인접행렬 구현 : O(V^2) = O(V)
   2) 인접리스트 구현 : O(V+2E) = O(V+E)
2. BFS
   1) 인접행렬 구현 : O(V^2) = O(V)
   2) 인접리스트 구현 : O(V+2E) = O(V+E)

코드

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

using namespace std;
//bfs를 여러번 하면서 컴포넌트의 수를 구해보자!
int consists_of[200]={0};//어떤 컴포넌트에 소속돼있는가(방문여부 포함)
//범위는 0-199
int n_com;

int get_seed(){
    for(int i = 0;i<n_com;i++){
        if(consists_of[i]==0){
            return i;
        }
    }
    return -1;
}

void bfs(int seed,vector<vector<int>> & computers,int comp){
    queue<int> q;
    q.push(seed);
    //넣을 때 visited 체크
    consists_of[seed] = comp;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        vector<int> children = computers[cur];
        for(int child = 0;child<children.size();child++){
            if(children[child] == 1&&consists_of[child]==0&&child!= cur){
                q.push(child);
                consists_of[child] = comp;
            }
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    n_com = n;
    int seed = get_seed();
    int comp = 1;
    
    while(seed !=-1){
        bfs(seed, computers, comp);
        seed = get_seed();
        
        comp++;
    }

    answer = comp-1;
    return answer;
}