[ 백준 ][ 골드2 ] 4195번 - 친구 네트워크 ( 파이썬 )

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

4195번: 친구 네트워크

 

문제

---

 

코드

---

import sys
input = sys.stdin.readline

def union(a,b):
    a, b = find(a), find(b)
    if a == b:
        return network[a]
    parents[b] = a
    network[a] += network[b]
    return network[a]

def find(node):
    if parents[node] != node:
        parents[node] = find(parents[node])
    return parents[node]

for _ in range(int(input())):
    parents, network = dict(), dict()
    for i in range(int(input())):
        a,b = input().split()
        if a not in parents.keys():
            parents[a], network[a] = a, 1
        if b not in parents.keys():
            parents[b], network[b] = b, 1
        print(union(a,b))

 

풀이

---

기존의 유니온파인드의 경우는 인덱스로 관계를 표현할 수 있었지만 이 문제는 문자열로 표현해야 하기 때문에 배열이 아닌 딕셔너리 형태로 부모관계를 표현한다.

최종적으로 친구 네트워크 수를 출력해야 하는데 모든 네트워크를 계산하려면 메모리 초과가 나올 것이 분명하다. 따라서 개수만 출력하기 위해 네트워크 수를 value로 갖는 딕셔너리를 추가한다.

유니온 파인드에서 부모노드가 되는 기준이 있어야 하지 않을까 생각했는데 어떤 기준을 세우기가 애매했고 a,b가 있다면 앞에 있는 a를 기준으로 하는 것이 가장 간단할 것 같았다.

 

| Union-Find |

• a,b를 입력받고 두 문자열이 parents, network에 없다면 추가해준다.
• 이때, 처음에는 자기 자신을 부모로 설정하고 network의 개수는 자신밖게 없으니 1로 설정한다.
• find는 해당 노드의 루트노드를 반환해준다.
• union은 두 노드 a,b에 대해서 b의 루트 노드를 a의 루트노드로 바꿔준다. 이 과정을 통해서 b와 a가 속한 집합이 하나로 합쳐진다.
• 또한 a와 b의 네트워크 수를 합쳐주어 반환한다.