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

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

4195번: 친구 네트워크

 

 

문제 풀이

- union find 문제이다. => 이에 대한 함수식을 쓰지 못하면 풀기 힘들다. (union find 문제라는 것은 알았는데 한동안 안풀면 까먹기 일상이다.)

- 리스트를 이용하기보다(부모, 자식 모두 string name이 있어서 리스트로 index를 찾기는 너무 시간복잡도가 클 것 같다.) 딕셔너리(dict)을 이용하여 dict['name']= parents['name'] 이 나오도록 하고 같은 일촌 수(?)까지 알 수 있도록 num['name'] = 일촌 수 가 나오도록 코드를 작성한다.

 

CODE

import sys
input = sys.stdin.readline

def find(x):
    if x == parents[x]:
        return x
    else:
        root_x = find(parents[x])
        parents[x] = root_x
        return parents[x]
def union(x,y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parents[root_y] = root_x
        num[root_x] += num[root_y]
t = int(input())
for _ in range(t):
    f = int(input())
    parents = dict()
    num = dict()
    for _ in range(f):
        x, y = input().split()
        if x not in parents:
            parents[x] = x
            num[x] = 1
        if y not in parents:
            parents[y] = y
            num[y] = 1
        union(x,y)
        print(num[find(x)])