[알고리즘] 백준 18116 Python

 

분류

유니온 파인드, 분리 집합

혼자 힘으로 해결 했는가?

△

느낀 점

유니온 파인드 문제인데, 기본적인 유니온 파인드가 아니다.

 

스스로 유니온 파인드 자체를 변경하는 2가지 경우를 고민 해 보았다.

 

1. 집합의 크기를 구하기

2. 집합의 원소를 구하기

 

1번의 경우는 라이님의 블로그를 참고했다.

https://blog.naver.com/kks227/220791837179

유니온 파인드(Union-Find) (수정: 2020-08-03)

 

2번의 경우는 gpt를 통해 구현을 해서 코드를 해석했다.

 

이 문제는 기본적인 유니온 파인드에서 더 나아가 집합의 갯수를 체크해야 한다.

 

라이님의 블로그를 통해 해당 주제에 대해 알고 있었기 때문에 내가 스스로 해결했다고 할수가 없었다.

 

다른 유니온 파인드의 응용 문제를 더 풀어야 겠다.

---

 

내가 작성한 코드

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(1000000)

N = int(input())

p = [-1 for _ in range(10**6 + 1)]


def find(x):
    if p[x] < 0: return x
    p[x] = find(p[x])
    return p[x]


def union(x, y):
    x = find(x) # x
    y = find(y) # y
    if x == y:
        return
    p[x] += p[y] # p[x] = -2 -> x가 루트,
    p[y] = x # p[y] = x


for i in range(N):
    command = list(stdin.readline().rstrip().split())

    if command[0] == 'I':
        union(int(command[1]), int(command[2]))
    else:
        root = find(int(command[1]))
        print(abs(p[root]))

 

 

 

---

비슷한 문제들