[Union_find][Algorithm] 백준 4195. 친구네트워크

   Union_find를 사용해서 푸는 문제들을 여러 풀면서 정리해 보았다. 문제를 간단히 정리하자면, input으로 들어오는 두 친구 정보 (ex. ("Fred", "Barney")) 사이에 존재하는 친구 수를 구하는 문제이다. 다만, 이 입력되는 친구가 서로 이미 친구라고 가정한다. 또한, 친구 수에는 본인도 포함한다. 따라서, Fred는 Barney는 본인을 포함하여 최소 2의 값을 가진다. 

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

4195번: 친구 네트워크

기존에 있는 집합(특정 친구 네트워크)을 활용하여 풀어야 하기 때문에 Union-find 알고리즘으로 이 문제를 접근할 수 있다.

1) 먼저, 이 문제를 푸는 기본 자료 구조로 특정 친구가 포함되어 있는 집합을 가리키고 있는 부분에 해당하는 부분을 딕셔너리를 사용할 수 있다. 그리고, 입력으로 들어오는 친구 정보에서 초기값은 본인 자신을 가르킨다.

parents = {}
cnt = {}

#parents[friend1] = friend1

2) 우리는 입력받은 두 친구를 이미 친구라고 가정하기 때문에 둘을 하나의 집합으로 합쳐주어야 한다. 이 경우, 왼쪽의 친구 노드 집합에 합친다. 초기값을 Fred는 Barney으로 받으면, {"Fred":"Fred", "Barney":"Barney"}로 받았다가, {"Fred":"Fred", "Barney":"Fred"}로 변경해준다. 바로 이 부분이 Union 메서드에 구현해야 할 내용이다. 

 

3) 최종적으로 우리가 return 해야 하는 값은 친구 네트워크에 속한 친구 수이므로, cnt에 딕셔너리 형태로 해당 집합에 속한 친구 수를 구한다. 

import sys
input = sys.stdin.readline

def find(parents,x):
    if parents[x] == x:
        return x
    new = find(parents, parents[x])
    parents[x] = new
    return new

def union(parnets,x1,x2,cnt):
    a = find(parents, x1)
    b = find(parents, x2)
    if a != b:
        parents[b] = a
        cnt[a] += cnt[b]
    
for _ in range(int(input())):
    parents = {}
    cnt = {}
    for test in range(int(input())):
        friend1, friend2 = input().split()

        if friend1 not in parents:
            parents[friend1] = friend1
            cnt[friend1] = 1

        if friend2 not in parents:
            parents[friend2] = friend2
            cnt[friend2] = 1

        union(parents, friend1, friend2, cnt)
        print(cnt[find(parents, friend1)])  

 

시행착오)

Union-find로 풀지 않고 일일이 각각의 집합을 만들어서 update하는 식으로 푼 경우 -> 런타임 에러(정확한 원인은 알지 못함/탐구중)

import sys
input = sys.stdin.readline

test_number = input()

F = []

while test_number !=0:
    test_number -= 1
    temp = sys.stdin.readline()
    f = [tuple(sys.stdin.readline().split()) for i in range(temp)]
    F.append(f)



def friends_n(temp):
    
    Facebook = {}
    answer = []
    for j in range(len(temp)):
        if temp[j][0] not in Facebook and temp[j][0] not in Facebook:
            Facebook[temp[j][0]],Facebook[temp[j][1]] = {temp[j][0], temp[j][1]}, {temp[j][0], temp[j][1]}             
            answer.append(2)
            
        elif temp[j][0] in Facebook and temp[j][1] in Facebook:
            Facebook[temp[j][0]].update(Facebook[temp[j][1]])
            Facebook[temp[j][0]].add(temp[j][1])
            answer.append(len(list(Facebook[temp[j][0]])))
             
            
        
        else:
            if temp[j][0] in Facebook:
                Facebook[temp[j][0]].add(temp[j][1])
                Facebook[temp[j][1]] = Facebook[temp[j][0]]
                answer.append(len(list(Facebook[temp[j][0]])))
                 
            else: 
                Facebook[temp[j][1]].add(temp[j][0])
                Facebook[temp[j][0]] = Facebook[temp[j][1]]
                answer.append(len(list(Facebook[temp[j][0]])))
                
    return answer
                 
        #print(Facebook)
        
for i in range(len(F)):
    answer = friends_n(F[i])
    
    for j in answer:
        print(j)