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

백준 - 4195 친구 네트워크

 

문제

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

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

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

입력

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

출력

 

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

 

 

문제해결방법 - 

 

 

1. 유니온 파인드(Union Find) 알고리즘으로 해결한다. 

2. 문제가 구체적으로 이해가 잘 안되는데 카카오톡 채팅방 개설로 생각하면 편하다.

3. 자료구조는 카운트를 반영할 리스트와 딕셔너리로 { " 이름 " : 방장 } 를 저장하는 구조를 만든다.

- 딕셔너리 말고도 이름 리스트를 만들고, parent 리스트를 만들어 이름에 대응하는 번호로 관리하는 방법도 가능하다.

- 유니온파인드로 연결될 때마다 이미 연결된 방장으로 연결되고, 카운트[방장]이 증가되는 구조이다.

- 방장만 친구관계의 수를 관리하고 있는 셈이다.

 

-코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def UNION(x, y):
	x = FIND(x)
	y = FIND(y)
	if x != y:
		parent[y] = x
		cnt[x] += cnt[y]
	print(cnt[x])

for _ in range(int(input())):
	parent, cnt = {}, {}
	for i in range(int(input())):
		a, b = map(str, input().split())
		if a not in parent:
			parent[a] = a
			cnt[a] = 1
		if b not in parent:
			parent[b] = b
			cnt[b] = 1
		UNION(a, b)