Gidhub BE Developer

[Programmers] 43162. 네트워크

2018-10-08
goodGid

Problem

Problem URL : 네트워크


[1] Answer Code (18. 10. 08)

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int p[201];

int Find(int x){
    if(x == p[x])
        return x;
    else{
        int y = Find(p[x]);
        p[x] = y;
        return p[x];
    }
    return x;
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    p[y] = x;
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0; i<n; i++)
        p[i] = i;
    
    int size = (int) computers.size();
    for(int i=0; i<size; i++){
        for(int j=0; j<n; j++){
            if(computers[i][j])
                Union(i,j);
        }
    }
    
    map<int,int> m;
    for(int i=0; i<n; i++){
        if( m[i] == 0 ){
            answer++;
            for(int j=0; j<n; j++){
                if(Find(i) == Find(j)){
                    m[j]++;
                }
            }
        }
    }   
    return answer;
}

Review

  • Union Find 알고리즘을 사용했다.

Back : NoSQL

Comments

Content