[L3] 프로그래머스 네트워크 C++ 유니온 파인드

리뷰

프로그래머스

연결된 컴퓨터끼리를 한개의 네트워크라 보고, 네트워크 집합의 개수를 구하는 문제

 

 

전역 변수

• nodes : 각 컴퓨터가 속한 네트워크의 번호를 저장하기 위한 정수형 배열, 크기는 200으로 초기화

 

함수

1. Find

int Find(int a)

 

노드가 속한 집합의 번호를 찾기 위한 함수

1. 매개변수로 탐색하고자 하는 노드의 번호를 a로 받아온다.
2. nodes의 a인덱스가 a라면 a를 리턴해 주면 된다.
3. 아닐 경우 재귀를 통해 탐색을 하며 경로 압축을 시켜준다.
4. 경로 압축을 통해 Find가 실행될때마다 경로가 최신화 된다.

 

2. Union

void Union(int a, int b)

 

두 노드간 네트워크 결합을 해주기 위한 함수

1. 두 노드를 매개변수 a, b로 각각 입력 받는다.
2. a와 b가 속한 집합의 정보를 Find함수를 통해 A, B로 받아준다.
3. 만약 A와 B가 동일하다면 이미 같은 집합에 속해 있기에 리턴해 준다.
4. 같은 집합에 속해있지 않다면 nodes의 B인덱스에 저장된 값을 A로 바꾸어 준다.

 

문제풀이

1. n개의 노드를 탐색하며 nodes배열을 자기자신의 인덱스를 값으로 갖도록 초기화 해준다.
2. 매개변수로 주어진 computers를 참조하며 Union작업을 해준다.
3. 만약 i와 j가 동일할 경우 자기 자신을 의미하므로 continue처리해 주면 된다.
4. computers[i][j]가 1일 경우 i와 j를 Union해주어 네트워크를 연결해 준다.
5. 중복이 불가능한 해시인 정수형 unordered_set을 dic으로 초기화 해준다.
6. n개의 노드를 탐색하며 자기자신이 속한 네트워크 집합의 번호를 dic에 추가해 준다.
7. dic의 크기를 리턴해 준다.

 

참고 사항

정수형 변수를 초깃값 1로 세팅하고 자신의 노드 번호와 nodes에 저장된 값이 다를 경우 증가시키는 형태로 해도 된다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int nodes[200];

int Find(int a) {
    if (nodes[a] == a) return a;
    return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
    int A = Find(a);
    int B = Find(b);
    if (A == B) return;
    nodes[B] = A;
}

int solution(int n, vector<vector<int>> computers) {
    for (int i = 0; i < n; i++) nodes[i] = i;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (computers[i][j]) Union(i, j);
        }
    }
    
    unordered_set<int> dic;
    for (int i = 0; i < n; i++) if (nodes[i] == i) dic.insert(i);
    return dic.size();
}