[백준][부분집합] 집합의 표현

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

내가 작성한 코드

# 시간초과
import sys
from collections import defaultdict
read = sys.stdin.readline

def check(idx, a, b):
    while a != idx[a]:
        a = idx[a]
    while b != idx[b]:
        b = idx[b]
    if a == b:
        print("YES")
    else:
        print("NO")

def union(idx, a, b):
    if a == b:
        return

    change_list = []
    while a != idx[a]:
        a = idx[a]
        change_list.append(a)
    change_list.append(a)
    while b != idx[b]:
        b = idx[b]
        change_list.append(b)
    change_list.append(b)

    for i in set(change_list):
        idx[i] = min(a,b)


n, m = list(map(int, read().rstrip().split(' ')))
idx = []

for k in range(n+1):
    idx.append(k)

for _ in range(m):
    k, a, b = list(map(int, read().rstrip().split(' ')))
    if k == 0:
        union(idx, a, b)
    else:
        check(idx, a, b)

• union : 집합을 대표하는 index(루트)로 소속되는 index들을 수정
• check : 두 index의 루트가 같은지 확인
• 그런데 계속 시간초과라서 여러 수정을 걸침

 

다른 사람이 작성한 코드

import sys

input = sys.stdin.readline

def get_parent(x):
    if parent[x] == x:
        return x
    p = get_parent(parent[x])
    parent[x] = p
    return p

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

    if x != y:
        parent[y] = x

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

n, m = map(int, input().split())
parent = {}

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

for _ in range(m):
    z, x, y = map(int, input().split())

    if not z:
        union(x, y)

    if z:
        if find_parent(x) == find_parent(y):
            print('YES')
        else:
            print('NO')

• 이 코드는 통과했다
• 기본적인 로직은 비슷하다
• 우선 모듈화가 이쁘다
• 시간차이의 원인
  • 이 코드는 union의 루트끼리 연결만함

https://chldkato.tistory.com/84

백준 1717 집합의 표현 (파이썬)

 

기억해야할 것

• 사소한 차이로 시간초과가 되기 때문에 디테일하게 풀어야함
  • 루트를 바꿔야하는 인덱스가 스스로 스택에 쌓임
  • 두 루트를 연결하고 끝남