[Python - Data Structure, Union Find] 1717 집합의 표현

2022. 9. 16. 16:25· Algorithm/Data Structure
목차
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드
  4. 📄 준비
  5. 📄 풀이

📌 문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

📌 출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

📌 문제 풀이

👨‍🏫 접근

합치기 연산 알고리즘으로 집합을 판별하는 전형적인 알고리즘이다.

 

문제처럼 집합이 주어졌을 때, 이 집합이 서로소인지 아닌지 판별하고 그 집합을 합치기 위해 사용한다. 먼저 "부모"라는 것을 설정해주도록 한다.

 

예를 들어, {1}, {2}, {3}, {4}, {5}, {6}, {7} 이라는 집합들이 있다고 할 때, 각각의 부모를 자기 자신으로 설정하는 것이다. 그래서 [1, 2, 3, 4, 5, 6, 7]  이라는 부모들이 존재한다.

 

이제 합치기 연산에서 이 부모가 큰 역할을 한다. {1}과 {3} 집합을 합한다고 하면, {1, 3}으로 간단하게 연산할 수 있지만, 코드상으로 구현하기 단순하지 않다. 그래서 이 부모 리스트를 통해 집합을 표현하는 것이다. 1과 3을 합친다고 한다면, 둘 중에 더 작은 값을 부모로 설정하는 것이다. 어떤 값을 부모로 설정할지는 중요하지 않아서 더 큰 값을 부모로 설정해도 된다.

 

각설하고 위의 연산을 마치면, [1, 2, 1, 4, 5, 6, 7] 이라는 부모 리스트가 만들어진다. 즉 집합의 세 번째 요소는 1을 부모로 한다는 것이다. 이 의미는 1과 3이 같은 집합에 속함임을 말해준다.

 

동일하게 4와 7을 합해준다. 그러면 [1, 2, 1, 4, 5, 6, 4]가 된다.

 

이제 3과 7을 합치는 연산을 해보자. 그러면 최종적으로 {1, 3, 4, 7}이라는 집합이 만들어진다. 이때 이를 구현하기 위해서는 3을 포함하는 집합과 7을 포함하는 집합의 부모를 찾아서 그 부모들끼리 다시 연산을 하는 것이다.

3의 부모는 1이며, 7의 부모는 4이다. 그래서 1과 4 중에 부모를 정한다고 하면 1이 부모가 되므로, 4의 부모는 1이 된다. 즉 최종적으로 [1, 2, 1, 1, 5, 6, 4] 의 부모 리스트가 만들어진다. 7번째 요소는 어차피 4를 부모로 가지므로, 4의 부모를 찾도록 연산하면 7도 {1, 3, 4, 7}에 속한다는 사실을 알 수 있다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

for i in range(m):
    com, a, b = map(int, input().split())
    if com == 0:
        union_parent(parent, a, b)
    else:
        if find_parent(parent, a) != find_parent(parent, b):
            print("NO")
        else:
            print("YES")

    print(parent)

📄 준비

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

부모를 찾는 연산을 해준다. 경로압축을 통해서 빠르게 부모를 찾아낸다.

 

그 이후로는 부모를 합치는 연산을 해준다. 이때, 각 요소들의 최종 조상을 찾아내서 합쳐준다.

 

부모는 자기자신으로 초기화해준다.

📄 풀이

for i in range(m):
    com, a, b = map(int, input().split())
    if com == 0:
        union_parent(parent, a, b)
    else:
        if find_parent(parent, a) != find_parent(parent, b):
            print("NO")
        else:
            print("YES")

    print(parent)

합치는 연산에서는 합쳐주고, 같은 집합인지 찾는 연산에서는 최종 조상을 찾는 연산을 해주어 같을 경우에만 YES를 출력하고 아니면 NO를 출력시킨다.

📌 총평

분리집합 연산을 까먹고 있었는데 이번 기회에 복습해서 기분이 좋다.

저작자표시 비영리 (새창열림)

'Algorithm > Data Structure' 카테고리의 다른 글

[Python - Data Structure, Union Find] 1976 여행 가자  (0) 2022.09.17
[Python - Data Structure, Map] 4195 - 친구 네트워크  (0) 2022.09.16
[Python - heapq] 1655 가운데를 말해요  (0) 2022.09.06
[Python - heapq] 11286 절댓값 힙  (0) 2022.09.05
[Python - Stack] 1874 스택 수열  (0) 2022.07.26
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드
  4. 📄 준비
  5. 📄 풀이
'Algorithm/Data Structure' 카테고리의 다른 글
  • [Python - Data Structure, Union Find] 1976 여행 가자
  • [Python - Data Structure, Map] 4195 - 친구 네트워크
  • [Python - heapq] 1655 가운데를 말해요
  • [Python - heapq] 11286 절댓값 힙
턴태
턴태
import { Dream } from "future";
턴태
턴태의 밑바닥부터 시작하는 de-vlog
턴태
전체
오늘
어제
  • ROOT (187)
    • Node.js (37)
      • ES6 (1)
      • TypeScript (3)
      • Express.js (16)
      • NestJS (16)
      • JS (24)
    • 프론트엔드 (29)
      • CS (5)
    • 백엔드 (1)
      • 검색 (2)
      • Database (1)
    • 기타 툴 (1)
      • git (1)
    • 데브옵스 & 인프라 (19)
      • Kubernetes (15)
      • Docker (2)
      • Monitoring (1)
      • IaC (1)
    • Algorithm (90)
      • Implementation & simulation (5)
      • Math (4)
      • Brute Force (1)
      • String (0)
      • Graph (5)
      • Recursion & Backtracking (19)
      • Divide & Conquer (2)
      • Dynamic Programming (18)
      • Greedy (13)
      • Priority Queue (2)
      • Binary Search (6)
      • Data Structure (7)
      • Shortest Path (5)
      • Minimum Spanning Tree (1)
      • Sorting (1)
      • Prefix Sum (1)
    • Linux (1)
      • Ubuntu (1)
    • Diary (5)
      • Algorithm (1)
      • Conference (1)
      • Retrospective (3)
    • Book (0)
      • Self-Development (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 오먹
  • 파이썬
  • 자바스크립트
  • TypeScript
  • python
  • 다이나믹 프로그래밍
  • 노드
  • Express
  • GREEDY
  • 함수형 프로그래밍
  • dynamic programming
  • 토이프로젝트
  • Kubernetes
  • 익스프레스
  • nestjs
  • node.js
  • N과 M
  • 백트래킹
  • k8s
  • 디프만
  • backtracking
  • Toy Project
  • Omuk
  • 인프런
  • 백준
  • 네스트
  • 쿠버네티스
  • baekjoon
  • 타입스크립트
  • 인프런X디프만

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
턴태
[Python - Data Structure, Union Find] 1717 집합의 표현
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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