4195_친구네트워크 ...반례?

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

4195번: 친구 네트워크

 

유니온 알고리즘을 활용하면 풀 수 있다.

 

 

우선 입력케이스로는 문자열이 나왔는데 이를 해결하기 위해서 딕셔너리를 사용해야 편하다.

 

즉, 사람 이름이 들어온다면 이를 인덱스로 삼는 형태로 해야 문제를 편하게 쓸 수 있다.

 

또한 친구네트워크의 개수가 필요한데, 나는 문제를 풀때 parents 딕셔너리안에 { ['이름' , 크기] } 식으로 저장했는데 문제를 풀고 생각해보니 그냥 조상을 저장하는 딕셔너리 한개와 크기값을 저장하는 딕셔너리 하나를 두는게 더 나았을 것 같기도 하다.

 

사람 두명을 입력받아서 둘을 union 연산을 하면 계속 조상이 합쳐질 것이다. 두 사람이 가지고 있는 네트워크 들의 합이 전체 네트워크의 합이 될 것이다. 효율적인 조상찾기를 위해서 카운터가 큰 값을 조상으로 넣어주었다.

 

다만 생각해줘야 할 경우가 있다. union 연산을 아무때나 하면 안된다. 만약 a,b라는 사람이 둘다 이미 같은 네트워크 안에 들어있다면 둘을 합치면 크기가 2배로 뛰게 될 것이다. 즉, a,b 라는 사람이 같은 네트워크 안에 있다면 union연산을 수행하면 안된다.

 

 

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
t=int(input())
def find(user):
    if parents[user][0] == user:
        return user
    parents[user][0] = find(parents[user][0])
    return parents[user][0]
def union(a,b):

    a,b = find(a),find(b)

    if parents[a][1] > parents[b][1]:
        parents[a][1] += parents[b][1]
        parents[b] = parents[a]
    else:
        parents[b][1] += parents[a][1]
        parents[a]= parents[b]

for _ in range(t):
    F = int(input())
    parents = {}
    for __ in range(F):
        users = list(map(str,input().split()))

        for user in users:
            if user not in parents:
                parents[user]=[user,1]

        if find(users[0]) != find(users[1]):
            union(users[0],users[1])
        print(parents[find(users[0])][1])
        #print(parents)

 

 

1
10
a b
a c
a d
a e
b c
b d
b e
c d
c e
d e

위 반례를 넣어보면 이미 같은 네트워크에 있는 사람을 넣었을때 예외처리가 잘 되어있는지 확인할 수 있다.

 

2
3
4
5
5
5
5
5
5
5

위 답이 나와야 한다.

 

1
9
a b
c d
e f
g h
b c
f g
d e
h a
b g

 

 

만약 출력할때 조상의 값을 안찾았다면 틀릴 수 있는데 위 코드를 돌려보면 이를 찾아볼 수 있다.

 

2
2
2
2
4
4
8
8
8

위 답처럼 나오게 해야한다.