프로그래머스 - 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

접근

dfs/bfs 항목에 있는 문제이지만, 보자마자 union find와 그래프가 떠올랐습니다.

굳이 따지자면 양방향 그래프인데, 그냥 union find만으로도 해결이 가능할 것 같았습니다.

따라서 각 노드를 순회하면서 자기보다 높은 번호의 노드와 연결되어 있다면 두 집합을 union시켰습니다.

문제

조금 실수해서 실패한 부분이 있었습니다.

최종 네트워크의 개수를 root가 몇개 있는지를 조사하는 방식으로 했는데,

두 노드가 모두 각자의 네트워크가 있고, 이 두 노드를 연결해야 할 때 union만 시켜준다면 최종결과에서 다시 한번더 부모노드를 찾아주어야 합니다.

예를들어 1번 노드가 3,4,5,6 에 연결되어있고,

2번 노드가 5,6에 연결되어 있다면

최종적으로는 1,2,3,4,5,6이 모두 연결된 하나의 네트워크를 구성해야 하지만

마지막에 다시 부모노드를 찾아 주지 않는다면

3,4번의 부모는 1번 노드이고, 1번노드의 부모는 2번노드이며

5,6번 노드의 부모는 2번노드가 되어

최종적으로 root의 개수는 1,2 인 2개가 나오게 됩니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <set>
using namespace std;

int u_find(int x);
void u_union(int x,int y);


int root[200];
int height[200];
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    set<int> res;
    for(int i = 0 ; i < n; i++){
        root[i] = i;
        height[i] = 0;
    }
    
    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++){
            
            if (computers[i][j] == 1) {
                u_union(i, j);
            }
        }
    }
    
    
    for(int i = 0 ; i < n; i++){
        root[i] = u_find(i);
        res.insert(root[i]);
    }
    answer = int(res.size());
    return answer;
}
int u_find(int x){
    if (root[x] == x) {
        return x;
    }else{
        return root[x] = u_find(root[x]);
    }
}
void u_union(int x,int y){
    
    x = u_find(x);
    y = u_find(y);
    
    
    if( x == y) return;
    
    if (height[x] <height[y]) {
        root[x] = y;
    }else{
        root[y] = x;
        if (height[x] == height[y]) {
            height[x]++;
        }
    }
}