[Python] 백준 4195 친구 네트워크

4195번: 친구 네트워크

유니온 파인드 : 부모를 숫자가 아닌 문자열로 바꾼다고 생각하면 쉽다. 그냥 똑같은 유니온 파인드 문제인데, 파이썬만 그런지 모르겠지만, for문에서 find함수를 써서 부모가 같은 친구들의 수를 카운트 했었는데 시간 초과가 나서 number라는 새로운 딕셔너리를 만들어서 친구의 수를 저장하도록 했다. 

 

1) parent 딕셔너리에 key = '친구이름', value = '친구이름'으로 초기화 해준다. 처음 입력 받을 때만 해야한다.

2) number 딕셔너리에 key = '친구이름', value = 1로 초기화 해준다. 처음 입력 받을 때만 한다.

3) 입력 받은 친구 이름 2개를 유니온 함수로 합친다. 

유니온 함수는 부모도 합치지만, 숫자도 합친다. 이때 주의할 점은key에 친구 이름을 value에 부모의 값을 담았다는 것을 잊지 말아야 한다. 유니온 파인드 문제는 항상 value에 부모를 넣는게 국룰인것 같다. 그래서 숫자를 합칠 때, key가 부모인 value에 접근해서 숫자를 더해주어야 한다.

4) 출력은 입력 받은 친구 이름의 부모의 숫자 value값을 해주면 된다. 

find함수를 사용해서 부모를 찾고, 그것을 number 딕셔너리에 넣어주면 부모의 자식 수를 알 수 있다. 친구 이름은 둘 중 아무거나 상관없는데, 이는 유니온 함수로 부모를 같게 만들었기 때문이다.

 

전체 코드

import sys
input = sys.stdin.readline


def parent_find(x):
    if x == parent[x]:
        return x
    y = parent_find(parent[x])
    parent[x] = y
    return y

def union(x,y):
    x = parent_find(x)
    y = parent_find(y)
    if x != y:
        parent[y] = x
        number[x] += number[y]

T = int(input())
for _ in range(T):
    F = int(input())
    parent = {}
    number = {}
    for _ in range(F):
        a, b = map(str, input().split())
        if a not in parent:
            parent[a] = a
            number[a] = 1
        if b not in parent:
            parent[b] = b
            number[b] = 1
        union(a,b)
        print(number[parent_find(a)])