[Union-Find] 프로그래머스 네트워크 C++

 

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

코딩테스트 연습 - 네트워크

 

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

using namespace std;

int parent[201];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

void unions(int x, int y) {
    x = find(x);
    y = find(y);
    
    // x!=y (x)
    if (x<y) parent[y] = x;
    else if (x>y) parent[x] = y;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0; i<n; i++) parent[i] = i;
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) { // j=i+1 (x), j=n-1 (o) 
            if ((computers[i][j] == 1) && (i!=j)) 
            	unions(i, j);
        }
    }
    
    // 9번 tc 해결
    for(int i=0; i<n; i++) parent[i] = find(i);
 
    sort(parent, parent+n);
    answer++;
    
    for(int i=0; i<n-1; i++) {
        if (parent[i] != parent[i+1]) answer++;
    }
    
    return answer;
}

---

※ DFS 풀이

https://whyou-story.tistory.com/64

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