[백준 1717번 골드5/PY] 집합의 표현

문제 출처

백준 1717번: 집합의 표현

나의 풀이

union-find.

참고로 파이썬 재귀는 엄청 얕은 편이라고 한다. 그래서
sys.setrecursionlimit(10 ** 6)와 같은 설정을 넣어서 재귀 깊이를 늘려야 한다고 한다.

import sys

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = map(int, input().split())

parent = [i for i in range(n + 1)]


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


def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[b] = a


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

파이썬으로 백준 입출력 받기 정리

https://paris-in-the-rain.tistory.com/72

import sys 

input = sys.stdin.readline

n, m = map(int, input().split())

for _ in range(m):
    opr, a, b = map(int, input().split())

vscode에서 입출력 txt 파일로 보면서 하려면
sys.stdin = open("input.txt", "r") 추가해주면 된다.

공백을 기준으로 구분된 데이터가 많지 않으면 그냥
a, b, c = map(int, input().split())으로 가져오고
데이터가 많다면 list(map(int, input().split())

2차원 배열 같은 거 받으려면

[list(map(int, input().split())) for _ in range(n)]

이번 문제처럼 그냥 단순히 여러 줄로 되어 있고, 각 줄은 구분된 데이터가 많지 않으면 아래처럼 꺼내쓰면 된다.

for _ in range(m):
    op, a, b = map(int, input().split())

파이썬 for 반복문 정리

https://wikidocs.net/22

# 전형적인 for 문
a = ['one', 'two', 'three']
for item in a:
    print(item)

# for문 응용
b = [(1, 2), (3, 4), (5, 6)]
for (first, last) in b:
    print(first, last)

# range 함수로 index 활용
c = 0
for i in range(1, 11):
    print(c)
    c = c + i

for index in range(len(a)):
    print(a[index])

# List comprehension
d = [1, 2, 3, 4, 5]
result = [num * 3 for num in d]
result2 = [num * 3 for num in d if num % 2 == 0]  # 이렇게 조건문을 붙일 수도 있다.
print(result, result2)

union-find 알고리즘 정리

https://m.blog.naver.com/ndb796/221230967614

union-find는 대표적인 그래프 알고리즘.
합집합 찾기 혹은 서로소 집합(disjoint-set) 알고리즘이라고도 한다.

여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

find 알고리즘은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘이다.

parent = [i for i in range(1, 11)]


def getParent(x):
    if parent[x] == x:
        return x
    return getParent(parent[x])


def unionParent(a, b):
    a = getParent(a)
    b = getParent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def findParent(a, b):
    a = getParent(a)
    b = getParent(b)

    if a == b:
        return 1
    else:
        return 0

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

union 함수의 경우 가장 기본적인 형태.
인자로 받은 두 값의 root를 찾고, 그걸 한쪽에 대입하는 로직.

union1 함수는 union 연산을 최적화한 형태.
rank 리스트에는 트리의 높이가 저장된다. 그래서 일단 전부 0으로 초기화해준다.

• union-by-rank 최적화인데,
  항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다.
  즉, 높이가 더 높은 쪽을 root로 삼는다.
  만약 두 인자의 높이가 같으면, 합쳤을 때 높이가 +1 된다.

union2 함수는 두 원소가 속한 트리의 전체 노드 수를 구하는 함수다.

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = map(int, input().split())

root = [i for i in range(n + 1)]
rank = [0 for i in range(n + 1)]
nodeCount = [1 for i in range(n + 1)]


def find(x):
    if root[x] == x:
        return x
    else:
        return find(root[x])


def union(x, y):
    x = find(x)
    y = find(y)

    root[y] = x


def union1(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if rank[x] < rank[y]:
        root[x] = y
    else:
        root[y] = x

        if rank[x] == rank[y]:
            rank[x] += 1


def union2(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        root[y] = x # y의 root를 x로 변경 
        nodeCount[x] += nodeCount[y] # x의 node 수에 y의 node 수를 더한다. 
        nodeCount[y] = 1 # x에 붙은 y의 node 수는 1로 초기화 

    return nodeCount[x] # 가장 root의 node 수 반환 


for _ in range(m):
    op, a, b = map(int, input().split())

    if op == 0:
        union1(a, b)

    else:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")