[백준/4195/파이썬] 친구 네트워크

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

4195번: 친구 네트워크

Problem

• 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
• 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

조건

• 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
• 첫째 줄에 테스트 케이스의 개수가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다.
• 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

SOL

이 문제도 , 그래프 그림을 그리다보면,  친구관계라는 합집합의 크기를 구해주는 문제이다.

일반적으로 , 인접행렬/인접리스트로 구현한다면 문제점이 2가지가 있다.

 

1.  친구들이 몇명있는지 정확하지가 않다. 입력에는 단지 2명의 사람의 관계만 지속적으로 주어질 뿐, 친구가 정확히 몇명인지 나오지 않았다. 따라서, adj의 크기를 정해주기 쉽지않다.(간선 +1개 만큼 정해도 될거 같긴하다)
2. 친구들이 문자열(아이디)로 주어진다. 인접행렬/리스트 모두 1번노드,2번노드와 같이 N번째 노드로 주어진다.따라서, 이와 같이 사용자 아이디로 처리한다면, 인접행렬/리스트를 다른 방식으로 구현해야한다. 떠오르는게,dictionary정도? 배열과 쓰임도 비슷하지만, key만 안다면 접근은 엄청 빠르니까, 각각 사용자의 아이디를 key로하면 된다.

dictionary로 구현한다면, 1번 문제는 자동으로 해결이 된다.

 

친구관계의 크기를 정하기

 

친구 관계가 형성될 때마다, 그 친구 네트워크가 몇개인지 알아내야한다.  몇가지 예시를 들어보자.

그림판

위와 같은 친구관계가 순서대로 주어졌다고 하자. 그럼 출력이 어떻게 나올까? 2,2,3으로 나올것이다.

• Betty - Fred : 2 
• Bill - Bro : 2
• Bro - Mapin:3

일반적인 그래프 풀이??

인접행렬을 구현 -> 그래프 탐색의 과정을 거칠건데, Bill -Bro - Mapin의 관계는 입력 받을 때, Bro- Mapin을 입력받는데, Bro에 연결된 모든 친구들을 봐야한다. 즉, 관계가 형성 될 때마다, BFS를 탐색해줘야한다.

인접 리스트로 구현한다면, O(V+E) , 이걸 F번 해줘야 하므로, F*O(F) , O(F^2)과 같다. 무적권 TL이 발생한다.

 

그리고, 이러한 Format은 익숙하다. 어떤 노드에 계속 다른 노드들이 합쳐지면서 , 하나의 관계를 나타내는 거.(여행그룹이라던지, 친구라던지, 등등) 관계를 효율좋게 나타내는 자료구조 Union-Find 구조를 이용하면 된다.

 

정리

• Dictionary로 그래프 구현
• union Find 구조 이용

#친구 네트워크
import sys
input= sys.stdin.readline
tc = int(input().rstrip())
#union의 size를 기록하는 technic!
#parent형태를 배열 뿐만아니라, dictionary 형태로도 기록이 가능하다.
def init(friend):
    parent[friend] = friend
    number[friend] = 1

def find(target):
    if target==parent[target]:
        return target
    parent[target]=find(parent[target])
    return parent[target]

def union(a,b):
    a=find(a)
    b=find(b)
    if a !=b:
        parent[b]=a
        #union의 size를 기록하는 technic!
        number[a]+=number[b]

for _ in range(tc):
    parent=dict()
    number=dict()
    F = int(input().rstrip())
    for _ in range(F):
        f_1,f_2=input().rstrip().split()
        if f_1 not in parent:
            init(f_1)
        if f_2 not in parent:
            init(f_2)
        union(f_1,f_2)
        print(number[find(f_1)])