[백준] 친구 네트워크

출처:: www.acmicpc.net/problem/4195

분류:: unionfind

 

1. 문제 이해 및 해결과정

2. 풀이방법

  1. 유니온파인드 [python]

#친구 네트워크
#https://www.acmicpc.net/problem/4195
import sys
sys.stdin = open("input.txt","r")
tc=int(input())

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

def union_parent(a,b): #a가 b의 부모라는 것 전제
    a=find_parent(a)
    b=find_parent(b)
    if a!=b: #a의 부모노드와 b의 부모노드가 같지않으면
        parent[b]=a #b의 부모를 a로 설정
        cnt[a]+=cnt[b] #a의 친구관계 숫자에 b가 가지고 있던 친구 수 더해줌

for _ in range(tc):
    f=int(input()) #친구관계수
    parent=dict() #부모
    cnt=dict() #네트워크 친구수
    for _ in range(f):
        a,b=input().split()
        #입력받은 이름이 부모딕셔너리에 없는 경우
        #부모와 cnt 초기화 과정
        if a not in parent:
            parent[a]=a
            cnt[a]=1
        if b not in parent:
            parent[b]=b
            cnt[b]=1
        # print(parent)
        # print(cnt)

        union_parent(a,b)
        print(cnt[find_parent(a)])

 

3. 오답원인

  1. 원래 만들던 union함수를 이용하면, a b가 같은 집합에 있어도 또 합쳐지는 일이 발생한다

def union_parent(parent,a,b): #기존의 union
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

 

4. 알게된 점