[백준 알고리즘] - 친구 네트워크 (4195번) with Union Find 알고리즘

문제

 

 

풀이 과정의 고민

 

이 문제는 단순한 구현 문제가 아니라 Union Find의 개념을 이해해야 풀기 쉬웠어요. 

Union Find의 개념을 간단히 설명해볼게요.

 

키 포인트는 노드 간에 부모 - 자식 관계를 만드는 거예요.

즉, 같은 그룹인지 확인하는 방법을 같은 부모를 가지고 있는지 확인하는 것으로 대신하는 거죠.

쉽게 생각하면 같은 그룹에 속할 경우 그 요소들에 그룹 번호를 부여한다고 볼 수도 있는데, 그 그룹 번호가 새롭게 생성되는 것이 아닌 특정 요소를 부모로 해서 그 요소 자체를 그룹 번호로 설정하는 거예요.

예시를 통해 살펴볼게요.

 

아래와 같이 4개의 노드가 존재한다고 가정해요.

 

 

 이 상태에서는 어떤 연결도 없기 때문에 각 노드의 부모는 자기 자신이 될 거예요.

 

노드	1	2	3	4
부모	1	2	3	4

 

그런데 1번 4번이 연결된 상태가 추가된다고 하면

 

 

 4번 노드의 부모 노드를 1번 노드로 변경해요.

 

노드	1	2	3	4
부모	1	2	3	4 1

 이제 부모 노드를 살펴보았을 때 [1, 2, 3] 세 가지 종류의 요소가 존재하므로 총그룹의 수는 3가지가 될 거예요.

이걸 코드로 풀어볼게요. 편의상 1, 2, 3, 4를 인덱스대로 0, 1, 2, 3에 매칭 시켜 구현해볼게요.

 

def find(x):
    if x == parent[x]:
        return x
    else:
        my_parent = find(parent[x])
        parent[x] = my_parent
        return parent[x]


def union(x, y):
    x = find(x)
    y = find(y)
    parent[y] = x


parent = [i for i in range(4)]

union(0, 3) # 1번 노드와 4번 노드를 연결

print(len(set(parent))) # 3 출력

 

여기서 헷갈릴 수 있는 부분은 연속해서 Union을 할 때 어떤 것을 parent로 둘 지의 기준이에요.

뭔가 막연하게 1과 4를 연결했을 때 4의 부모를 1로 두는 것과 1의 부모를 4로 두는 것이 다른 결과를 낼 수 있다고 생각이 들기 때문이에요. 그런데 Union Find에서 찾고자 하는 것은 누가 부모냐의 문제가 아니라 그룹의 개수이기 때문에 문제가 되지 않아요. 위의 예시에서 부모가 [1, 2, 3, 1]이 되는 것이나 [4, 2, 3, 4]가 되는 것이나 모두 결론은 3개가 돼서 같은 결론이 돼요 :]

 

이제 이 개념을 기반으로 문제를 풀어볼게요!

 

풀이

def find(x):
    if x == parent[x]:
        return x
    else:
        my_parent = find(parent[x])
        parent[x] = my_parent
        return parent[x]

def union(x, y):
    parent_x = find(x)
    parent_y = find(y)

    if parent_x != parent_y:
        parent[parent_y] = parent_x
        number[parent_x] += number[parent_y] # 그룹에 인원 수 추가


from sys import stdin

input = stdin.readline

T = int(input())
for _ in range(T):

    parent, number = {}, {}

    F = int(input())
    for _ in range(F):
        f1, f2 = input().split()

        if f1 not in parent:
            parent[f1] = f1
            number[f1] = 1
        if f2 not in parent:
            parent[f2] = f2
            number[f2] = 1

        union(f1, f2)

        print(number[find(f1)])

 

 

문제 풀이 해설

위의 풀이를 기준으로 parent와 number를 출력해볼게요.

 

 

여기서 헷갈릴 수 있는 부분은 number에 나타난 숫자 값이에요. 

저 자료를 단순히 "Betty: 1"이라고 해서 "Betty라는 parent가 1명"이라고 해석하면 안돼요.

기준을 Wilma로 세웠기 때문에 Wilma의 number에 Betty의 number가 더해지는 순간 "Betty:1"은 의미가 없는 값이 돼요. 어차피 Betty에 접근해도 그 부모인 Wilma의 숫자로 계산될 것이기 때문이에요.

 

그래서 풀이에서 중요한 것은 union의 방향인데 union(x, y)에서 number[x] <- number[y] 방향으로 흡수되는 구조이기 때문에 마지막 출력도 반드시 왼쪽 요소인 f1을 출력해줘야 해요. 여기서 f2를 출력하면 union이 반영되지 않은 값이 나오는 것이죠.

 

즉, number라는 자료는 단순히 각 키를 parent로 하는 자료들의 집합이 아니라 병합되기 이전의 그룹 수(Dummy 값)도 포함한 자료이므로 꺼내올 때 그 순서를 잘 고려해야 하는 자료인 것이죠.

 

또 중요한 것은 parent 자료인데 Betty의 parent는 여전히 Fred가 아닌 Wilma라는 것을 확인할 수 있죠. 즉, Union Find에서는 자료를 매번 갱신해서 최상위 parent로 만들어주는 것이 아니라 바로 위 노드 부모는 유지하되 검색할 때에는 찾을 수 있게 만들어주는 구조예요.

 

문제 출처

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