[Python] G2_4195_친구 네트워크 👬

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

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

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

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제

코드

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

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

def union(a,b):
    a,b = find(a),find(b)
    if a != b:
        parent[b] = a # 부모 노드 변경
        num[a] += num[b] # 친구 수를 합쳐줌
 
T = int(input())
for _ in range(T):
    N = int(input())
    parent = dict()
    num = dict()
    
    for _ in range(N):
        person1,person2 = input().split()
        # 노드 지정
        if person1 not in parent:
            parent[person1] = person1
            num[person1] = 1
        if person2 not in parent:
            parent[person2] = person2
            num[person2] = 1
        # 지정한 노드로 union   
        union(person1,person2)
        # 친구 네트워크에 몇 명이 있는지 확인
        print(num[find(person1)])

이 문제는 입력마다 유니온 파인드를 실행하며, 해당하는 그룹에 속해 있는 사람의 수를 출력해주야 한다.

• 부모 노드의 번호인 parent와 그룹의 사람 수 num을 만들어준다.

• 입력을 받으며, 만약 처음 나온 사람의 이름이라면 자기 자신을 부모 노드로 하고 사람의 수가 1인 그룹을 만들어준다.

• 두 사람을 union 하며 그룹을 합쳐준다.

• 합치며 person1으로 부모노드가 변경되고, 두 그룹의 사람 수 또한 합쳐진다.

if a != b:
        parent[b] = a # 부모 노드 변경
        num[a] += num[b] # 친구 수를 합쳐줌

• 그룹의 수가 합쳐졌으니, 마지막으로 person1 그룹의 사람 수를 출력해준다.

느낀 점 & 배운 점

1. 부모 노드와 사람 수를 따로 사전으로 관리해주며, 앞으로도 이런 식으로 접근해야겠구나라는 생각이 들었다!