네트워크 - 프로그래머스

문제 

난이도 : 프로그래머스 3단계

정답률 : 60%

분류 : DFS, BFS, Union-Find(서로소 집합)

 

문제 리뷰

보자마자, 유니온 파인드 문제라고 생각했다.

기존에 구현했던 유니온 파인드의 경우,

1. X에 포함 되는 (X + n) 번 째 원소가 있다고 가정하고,

2. Y에 X를 Union하는 상태를 가정하면,

Y <- X

X <- X + n 

이런 식으로 아직 X+n은 X를 가르키고 있다. 

따라서 문제 케이스에 맞지 않았다!

그래서 일단은 주먹구구식으로 가르키는 모든 경우를 순회해서 바꿔주었다.

더 좋은 방법이 있는지는 고민해볼만하다.

문제 소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int Root[210];
int N;
int Find(int x){
    if(x == Root[x]) return x;
    return Root[x] = Find(Root[x]);
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x > y){
        Root[x] = y;
        for(int i = 0; i < N; i++){
            if(Root[i] == x) Root[i] = y;
        }
    }else if(x < y){
        Root[y] = x;
        for(int i = 0; i < N; i++){
            if(Root[i] == y) Root[i] = x;
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    set<int> Sets;
    N= n;
    for(int i = 0; i < 210; i++){
        Root[i] = i;
    }
    
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < n; j++){
            if(computers[i][j] == 1){
                Union(i,j);
            }
        }
    }
    Sets.insert(99999999);
    for(int i = 0; i < n; i++){
        if(find(Sets.begin(), Sets.end(), Root[i]) == Sets.end()){
            answer++;
            Sets.insert(Root[i]);
        }
        cout << Root[i] << endl;
    }
    return answer;
}