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

[문제]

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

 

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

[풀이]

 

1) 서로소집합(union-find)로 트리 형태의 집합을 구한다. 

 

2) computers[i][j] == 1인 경우에는 연결되어있다는 표시이므로 같은 부모를 가진 경우 (이미 같은 집합)가 아닌 경우에는 같은 집합으로 합쳐준다. 

트리이기 때문에 사이클 형성이 되면 안된다.

 

3) 모든 컴퓨터들이 연결되어있지 않는 경우 (최대 N) 에서 집합으로 합쳐준 경우를 제거해주면 집합의 개수를 구할 수 있다. 

 

---

#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <iostream>
 
using namespace std;
 
int parent[201];
 
void init(int n) {
    for (int i = 1; i <=n; i++ ) {
        parent[i] = i;
    }
}
 
int find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a]);
}
    
void union_find(int a, int b) {
    int roota = find(a);
    int rootb = find(b);
    
    parent[roota] = rootb;
}
bool same_parent(int a, int b) {
    int roota = find(a);
    int rootb = find(b);
    if (roota == rootb) return true;
    return false;
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
 
    init(n);
    int idx = 1, combine = 0;
    for (int i = 0; i < computers.size(); i++) {
        // 1번 컴퓨터부터 연결정보를 알려준다. 
        for (int j =0; j < n; j++) {
            if (computers[i][j] == 1) {
                //연결되어있다. -> 같은 집합에 넣어준다. 
                if (!same_parent(idx, j+1)){
                    combine++;
                    union_find(idx, j+1);
                }
            }
        }
        idx++;
    }
 
    answer = n-combine;
    return answer;
    
}