[프로그래머스 - 네트워크] BFS, 분리집합(disjoint set) Union & Find C++

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다.

 

컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 

 

연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. 

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int parent[200];
map <int,int> m;

int Find(int x){
    if(x==parent[x]) return x;
    return parent[x] = Find(parent[x]);
}
void Union(int x, int y){
    int px = Find(x);
    int py = Find(y);
    if(px != py){
        parent[px] = py;
    }
}
int solution(int n, vector<vector<int>> comps) {
    int answer = 0;
    for(int i=0;i<n;i++){
        parent[i]=i;
    }
    for(int i=0;i<n;i++){
        for(int j= i+1 ; j<n ; j++){
            if(comps[i][j] == 1){
                Union(i,j);
            }
        }
    }
    for(int i=0;i<n;i++){
        int n = Find(i);
        if(m.find(n) == m.end()){
            //m[n]++;
            answer++;
        }
        else{
            m[n] =1;
        }
    }
    return answer;
}