[알고리즘] 백준 4195 Python

 

분류

유니온 파인드, 분리 집합

혼자 힘으로 해결 했는가?

O

느낀 점

 

18116번의 응용 형태이다.

이 문제는 집합의 표현이 다소 까다롭다.

보통은 가능한 집합의 원소를 모두 알려주고 시작하지만, 이 문제는 그 때 그 때 해결을 해야한다.

 

따라서 집합의 표현을 배열이 아닌 딕셔너리로 표현했다.

그리고 타입 때문에 골치가 아팠다.

 

이 문제에서 함정인 부분은 바로 a e가 입력으로 들어온 후 e a가 입력으로 들어온 경우이다.

 

처음은 union 함수에서 이미 같은 함수이면 아무것도 리턴을 하지 않았다가

44%에서 Type Error가 발생했다.

 

그 이유는 a e를 유니온 후 e a가 입력으로 온 경우 이미 같은 집합이기에 None을 리턴했고

이 때문에 타입 에러가 발생했다.

 

그냥 이미 친구인 관계에 대해서도 몇명인지 출력하면 된다.

---

 

내가 작성한 코드

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(100001)

T = int(input())


def find(x):
    if type(p[x][0]) is int and p[x][0] < 0: return x
    p[x][0] = find(p[x][0])
    return p[x][0]

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

    if x == y:
        return p[x][0]
    else:
        p[x][0] += p[y][0]
        p[y][0] = x
        return p[x][0]


p = {}
for i in range(T):
    p = {}
    rel = int(input())

    for i in range(rel):
        a, b = stdin.readline().rstrip().split()

        if a not in p:
            p[a] = [-1]
        if b not in p:
            p[b] = [-1]

        print(abs(union(a,b)))

 

 

 

---

비슷한 문제들

 

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

18116번: 로봇 조립