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

문제

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

풀이

Union-Find 알고리즘은 잘 짰는데 문제에서 주어진 2차원 배열에 접근할 때,
[[1, 1, 0], [1, 1, 0], [0, 0, 1]]

1 2
1 3
2 1
2 3
3 1
3 2
이런 인덱스 번호로 Union 함수 인자를 넘겨줘야 하는데 쉬운건데 for문에서 괜히 해맴 ㅠ

원래는 DFS/BFS 유형으로 나온 문제임

코드

#include <string>
#include <vector>

using namespace std;

vector<int> root;

int Find(int node) {
    if(root[node] == node)
        return node;
    else
        return root[node] = Find(root[node]);
}

void Union(int a, int b) {
    int parent_a = Find(a);
    int parent_b = Find(b);
    
    root[parent_b] = parent_a;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = n;
    
    for(int i=0; i<=n; i++) {
        root.push_back(i);
    }
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if((i!=j) && (computers[i][j]))
                Union(i+1,j+1);
        }
    }
    
    for(int i=1; i<=n; i++) {
        if(root[i] != i)
            answer--;
    }
 
    return answer;
}