[BOJ알고리즘, C++]#1717_집합의 표현, Union-Find, 유니온 파인드

2023. 12. 15. 22:10· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. 2. 풀이
  3. 1. Union-Find 알고리즘
  4. 2. 두 원소가 같은 집합이면 NO, 다른 집합이면 YES
  5. #3. 코드

 

#1. 문제

 

 

2. 풀이

 

1. Union-Find 알고리즘

 

[자료구조]#6_그래프

#0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와

webddevys.tistory.com

 

Details

 

[정의] : Union-Find 연산은 서로소 집합(Disjoint Set) 표현에 사용되는 알고리즘입니다.
[특징] : Find 연산은 원소가 속한 집합의 대표 원소를 찾고, Union 연산은 두 집합을 하나로 합칩니다.

2. 두 원소가 같은 집합이면 NO, 다른 집합이면 YES

 

  1. 먼저, Find 연산을 통해 두 원소의 대표 노드를 찾습니다.
  2. 두 원소의 대표 노드는 각 집합을 대표하며, 서로 다를 경우, Union 연산을 통해 하나로 합쳐줍니다.

 


 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, m;

// #1. Find 연산 : path-compression 최적화
int Find(int x, vector<int>& parent)
{
    if(parent[x] != x)
        parent[x] = Find(parent[x], parent);
    
    return parent[x];
}

// #2. Union 연산 : union-by-rank 최적화
void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{ 
    // rootX의 랭크 > rootY의 랭크 : rootX를 rootY의 parent로 변경
    if(rank[rootX] > rank[rootY])
    {
        parent[rootY] = rootX;
    }
    // rootX의 랭크 < rootY의 랭크 : rootY를 rootX의 parent로 변경
    else if(rank[rootX] < rank[rootY])
    {
        parent[rootX] = rootY;
    }
    // rootX의 랭크 = rootY의 랭크 : rootY를 rootX의 parent로 변경, rootY의 랭크 상승 +1
    else
    {
        parent[rootX] = rootY;
        rank[rootY]++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    
    // parent 목록 
    vector<int> parent(n+1);
    // parent 목록에서 해당 정점의 부모를 자신으로 초기화
    for(int i=0; i<=n; i++)
        parent[i] = i;
    // rank 목록, 0으로 초기화
    vector<int> rank(n+1, 0);
    
    int unionOrJoint = -1;
    while(cin >> unionOrJoint)
    {
        int a, b;
        cin >> a >> b;
        
        // #1. a와 b가 속해있는 집합의 루트 노드 찾기
        int rootX = Find(a, parent);
        int rootY = Find(b, parent);
        
        // #2. 합집합 연산 -> Union 연산
        if(unionOrJoint == 0)
        {
            // #1-1. 각 숫자의 루트 노드가 다르다면 서로 다른 집합으로 가정하고 Union 연산 수행
            if(rootX != rootY)
            {
                Union(rootX, rootY, parent, rank);
            }
        }
        // #3. 같은 집합 여부 -> Find 연산, 결과 출력
        else if(unionOrJoint == 1)
        {
            // #2-1. 서로 같은 루트 노드를 가지면, 같은 집합에 속해있음
            if(rootX == rootY)
            {
                cout << "YES" << '\n';
            }
            // #2-2. 서로 다른 루트 노드를 가지면, 다른 집합에 속해있음
            else
            {
                cout << "NO" << '\n';
            }
        }
    }
    
    return 0;
}

 


 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#1922_네트워크 연결, MST, 최소 신장 트리, 크루스칼, 프림, 솔린  (0) 2023.12.15
[BOJ알고리즘, C++]#1197_최소 스패닝 트리, MST, 크루스칼, 프림, 솔린  (0) 2023.12.15
[BOJ알고리즘, C++]#2805_나무 자르기, 이분 탐색  (0) 2023.12.14
[BOJ알고리즘, C++]#1260_DFS와 BFS, DFS, BFS  (0) 2023.12.14
[BOJ알고리즘, C++]#2606_바이러스, 그래프, DFS, BFS  (0) 2023.12.14
  1. #1. 문제
  2. 2. 풀이
  3. 1. Union-Find 알고리즘
  4. 2. 두 원소가 같은 집합이면 NO, 다른 집합이면 YES
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#1922_네트워크 연결, MST, 최소 신장 트리, 크루스칼, 프림, 솔린
  • [BOJ알고리즘, C++]#1197_최소 스패닝 트리, MST, 크루스칼, 프림, 솔린
  • [BOJ알고리즘, C++]#2805_나무 자르기, 이분 탐색
  • [BOJ알고리즘, C++]#1260_DFS와 BFS, DFS, BFS
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 우선순위 큐
  • stl
  • 트리
  • BFS
  • 기술 질문
  • 알고리즘
  • dfs
  • Effective C++
  • programmers
  • BOJ
  • 그래프
  • 정렬
  • 최단 경로
  • unreal
  • set
  • DP
  • 개발
  • C++
  • Unreal Blueprint
  • 디자인 패턴

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#1717_집합의 표현, Union-Find, 유니온 파인드
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.