c++ 알고리즘 스터디 2주차 - 유니온파인드

유니온 파인드 (union-find)

동빈나 유튜브로 예습하고 스터디장님 설명 듣고 문제풀려는데?! 기억이 안남

그래서 다시 동빈나 블로그로 예습함. ( m.blog.naver.com/ndb796/221230967614 )

 

1. 맨처음 부모노드를 자기 자신으로 초기화한다.

1	2	3	4
1	2	3	4

2. 주어진 두 인덱스에 대해서 부모노드가 다르다면 부모노드를 같게 만들어준다. → unionparents

인덱스번호가 더 작은 쪽으로 부모노드를 바꾸는 게 국룰인거 같습니다. 큰 쪽이어도 상관은 없음

EX) 1,3 번을 합하라

1	2	3	4
1	2	1	4

EX) 2,4 번을 합하라 

1	2	3	4
1	2	1	2

EX) 2,3번을 합하라 

1	2	3	4
1	1	1	2

 원래 2번이랑 4번은 부모노드가 2로 같았는데 2번의 부모노드가 1로 바뀐 상황이다.

그럼 4번도 부모노드가 1로 업데이트가 되어야한다.  즉 4번 기준으로 루트노드인 1이 나올떄까지 부모노드인 2의 부모노드를 또 찾아가야한다. 

 

단순하게 부모를 합치는 게 아니라 지금 부모노드가 루트노드인지 루트노드가 아니라면 업데이트를 해준 후에 합쳐줘야한다. 

int getparent(vector<int>& parent , int x){
    if (parent[x] == x) return x;
    return parent[x] = getparent(parent, parent[x]);
}

지금 자신의 부모노드가 루트노드인지 아닌지 확인해주는거다. 

1번 같은 경우 자신의 부모노드와 자신이 같다 → 즉 루트노드라는거다.

4번 같은 경우 자신의 부모노드가 자신과 다르므로, 자신의 부모노드를 따라가야한다. 

parent[4] = getparent(parent , 2) 가 된다. 

그러면 getparent(parent , 2) 를 시행하면 2번에 대해서 부모노드가 1이므로 애도 루트노드가 아니다. 

parent[2] = getparent(patent, 1) 이 된다.

1은 부모노드도 1, 즉 루트노드이다. 

그럼 parent[4] = getparent(parent , 2) = 1 로 업그레이드가 된다. 

 

업그레이드를 한 후 합쳐버리자~~ 

부모노드가 작은 쪽으로 바꿔버린다.

void unionparent(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x < y)parent[y] = x;
    else parent[x] = y;
}

 

가장 기본적인 백준 1717번을 풀어보자. 

백준 1717번 집합의 표현 (www.acmicpc.net/problem/1717)

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

using namespace std;
vector<int> parent;

//부모찾기
int getparent(vector<int>& parent , int x){
    if (parent[x] == x) return x;
    return parent[x] = getparent(parent, parent[x]);
}

//부모 합치기 
void unionparent(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x < y)parent[y] = x;
    else parent[x] = y;
}

int find(vector<int>&parent , int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x == y) return printf("YES\n");
    else return printf("NO\n");
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    //부모배열의 크기 resize
    parent.resize(n + 1);
    // 부모 배열 초기화
    for (int i = 1; i <=n ; i++)   parent[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d" ,&a, &b , &c);
        if (a == 0) unionparent(parent, b, c);
        else find(parent, b, c);
    }
}

 

백준 1976번 여행가자 ( www.acmicpc.net/problem/1976)

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

using namespace std;
vector<int> parent;
vector<int> plan;

//부모찾기
int getparent(vector<int>& parent, int x) {
    if (parent[x] == x) return x;
    return parent[x] = getparent(parent, parent[x]);
}

//부모 합치기 
void unionparent(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x < y)parent[y] = x;
    else parent[x] = y;
}

int find(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x == y) return 1;
    else return 0;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    //부모배열의 크기 resize
    parent.resize(n + 1);
    plan.resize(m);
    // 부모 배열 초기화
    for (int i = 1; i <= n; i++)   parent[i] = i;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int answer;
            scanf("%d", &answer);
            if (answer == 1) {
                unionparent(parent, i, j);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        scanf("%d", &plan[i]);
    }

    int trip = 1;

    for (int i = 0; i < m - 1; i++) {
        if (!find(parent, plan[i], plan[i + 1])) {
            trip = 0;
            break;
        }
    }
    if (trip) printf("YES");
    else printf("NO");
}

nxn 형태로 행렬의 (i,j) 가 1이면 i랑 j랑 이어져있다라고 알려준다는 거 말고는 크게 다른 건 없는 문제다.