[BOJ/Python] 4195_친구 네트워크

문제 출처:https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

문제

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

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

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

입력

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

출력

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

예제 입력 1

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력 1

2
3
4
2
2
4

---

풀이

 

• 이 문제에서 친구는 노드이고, 친구 관계가 생긴다는 것은 두 노드가 같은 집합에 속하게 됨을 의미한다.
• 따라서 Union&Find를 이용하여, 문제에서 주어지는 노드들을 하나의 집합으로 합치고, 그 집합에 속하는 노드의 개수를 출력하면 된다.
• 그런데 여기서 합치는 과정을 수행할 때마다 그 집합에 존재하는 노드의 개수를 출력해야 하는데, 각 노드마다 그 집합에 속하는지 find 함수를 통하여 구하게 되면 n개의 노드에 대하여 n번만큼 find 함수를 호출해야 하므로 효율적이지 않다.
• 따라서, 각 집합들에 존재하는 루트 노드가 해당 집합에 존재하는 노드의 개수를 저장하도록 하였다.
• 이렇게 되면 두 집합을 합칠 때 한 집합의 루트 노드가 다른 집합의 루트 노드의 자식으로 들어간다면, 기존에 갖고 있던 노드의 개수를 넘겨주면 된다.

 

만약 다음과 같은 입력이 들어올 경우에 대하여 생각해보자.

1

5

A B

C D

D E

B E

A E

 

1은 테스트 케이스의 개수이다.

총 5개의 친구 관계가 주어짐을 알 수 있다. 각 친구 관계에 대하여 살펴보면 다음과 같다.

 

우선 A B를 입력받았을 때의 경우이다.

• 해당 노드가 존재하지 않으므로, 생성해 준다.
• 각 노드의 부모 노드는 자기 자신으로 설정해 주고, 그러므로 루트 노드 또한 자기 자신이다.
• A와 B의 경우, 각각 노드가 하나인 집합이라고 생각할 수 있다.
• 두 노드를 union을 통해 하나의 집합으로 합치게 되면 다음과 같다.

 

 

 

• A와 B 중 A가 더 작다.(사전순으로 비교하였을 때 A가 B보다 빨리 나오기 때문이다.)
• 따라서 A와 B을 하나의 집합으로 합칠 경우, A가 B의 부모 노드가 된다.
• 여기서 기존에 B가 갖고 있던 1(B집합의 노드의 개수)을 A가 갖고 있던 1(A집합의 노드의 개수)에 더해준다.
• 결과적으로 A 집합에 속해있는 노드의 개수는 2 임을 알 수 있고, 2를 출력한다.

 

 

 

이어서 C D를 입력받았을 때의 경우이다.

• 마찬가지로 C, D 노드가 존재하지 않으므로, 생성해 준다.
• 각 노드의 부모 노드는 자기 자신으로 설정해 주고, 그러므로 루트 노드 또한 자기 자신이다.
• 두 노드를 union을 통해 하나의 집합으로 합치게 되면 다음과 같다.

 

 

 

• C와 D 중 C가 더 작으므로 C가 D의 부모 노드가 되고, 그 집합의 루트 노드가 된다.
• (C집합의 노드의 개수) += (D집합의 노드의 개수)가 된다.
• 결과적으로 C 집합에 속해있는 노드의 개수는 2 임을 알 수 있고, 2를 출력한다.

 

 

 

D E를 입력받았을 때의 경우이다.

• D 노드는 존재하지만, E노드는 존재하지 않으므로 생성해 준다.
• 두 노드를 union을 통해 하나의 집합으로 합치게 되면 다음과 같다.

 

 

 

• D노드의 부모노드는 C노드이고, E노드의 부모노드는 자기 자신인 E노드이다.
• 여기서 C와 E 중 C가 더 작으므로 C가 E의 부모 노드가 되고, 그 집합의 루트 노드가 된다.
• (C집합의 노드의 개수) += (E집합의 노드의 개수)가 된다.
• 결과적으로 C 집합에 속해있는 노드의 개수는 3 임을 알 수 있고, 3을 출력한다.

 

 

 

B E를 입력받았을 경우이다.

• 두 노드 모두 존재하므로 새로 생성되는 노드는 없다.
• 두 노드를 union을 통해 하나의 집합으로 합친다.
• 여기서 B노드가 속한 집합의 루트 노드는 A노드이다.
• E노드가 속한 집합의 루트 노드는 C노드이다.
• A노드와 C노드를 비교하였을 때, A노드가 더 작으므로 C노드의 부모 노드가 된다.

 

 

 

• 따라서 기존에 존재하던 A집합과 C집합을 합치는 것은 C집합이 A집합에 속하게 됨을 의미한다.
• 그러므로 (A집합의 노드의 개수) += (C집합의 노드의 개수)가 된다.
• 따라서 A집합의 노드의 개수는 5가 되고, 5를 출력한다.

 

 

 

마지막으로 A E의 경우이다.

• 이 경우 A의 경우, 자기 자신이 곧 부모이며 루트 노드이다.
• E의 경우, 루트 노드가 A이다.
• 따라서 두 노드는 같은 집합에 속해있으므로 노드의 개수를 추가하지 않는다.
• 그 집합의 루트 노드인 A가 갖고 있는 5를 출력한다.

 

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if x!=parent[x]:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union(parent,count,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        count[a] += count[b]
        parent[b] = a
    elif a>b:
        count[b] += count[a]
        parent[a] = b
        
 
t = int(sys.stdin.readline())
for _ in range(t):
    parent = {}
    count = {}
 
    f = int(sys.stdin.readline())
    for _ in range(f):
        a,b = sys.stdin.readline().split()
        
        if a not in parent:
            parent[a] = a
            count[a] = 1
        if b not in parent:
            parent[b] = b
            count[b] = 1
        
        union(parent,count,a,b)
        print(count[find_parent(parent,a)])

•  
• count를 이용하여 해당 그룹의 노드의 개수를 계산하였다.
• 만약 두 집합을 합칠 때 a <b의 경우라면, (b가 속한 집합의 노드의 개수)를 (a가 속한 집합의 노드의 개수)에 더해준다.
• a> b의 경우, (a가 속한 집합의 노드의 개수)를 (b가 속한 집합의 노드의 개수)에 더해준다.
• 여기서 만약 a==b 라면, 두 노드가 이미 같은 집합에 속해있으므로 노드의 개수를 더해주지 않는다.