[#4195] 친구 네트워크

RookieAND·2022년 12월 1일

백준 유니온파인드 코테 해시

BaekJoon

목록 보기

38/42

❓ Question

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

📖 Before Start

유니온 파인드 와 해시 자료구조를 활용하여 푸는 문제였다.

이번 문제는 딕셔너리 자료구조를 활용하여 유니온 파인드를 쓰는 문제였다.
유니온 파인드가 비교적 어려운 알고리즘이라 생각해서, 이를 계속 풀었다.

✒️ Design Algorithm

루트 노드 를 보관하는 변수를 딕셔너리로 설계해야 한다.

첫째 줄에 테스트 케이스의 개수 T 가 주어진다.
그리고, 각 케이스의 첫째 줄에는 관계의 수 F 가 주어진다.

다음 F 개의 줄에는 친구 관계에 놓인 아이디로 주어진다.
각 아이디는 알파벳 대문자 또는 소문자로만 이루어진 문자열이다.

친구 관계를 입력 받을 때마다 두 사람은 서로 친구 관계가 된 것이고,
두 사람이 구축한 친구 네트워크에 몇 명이 있는지를 계속 체크해야 한다.

기존의 유니온 파인드 문제를 풀때는 노드가 정수로 이루어진 경우가 많았는데,
이번에는 노드가 문자열로 이루어져 있어 이를 어떻게 처리해야 할지 고민했다.

결국 키와 값으로 관계를 묶는 해시 타입의 자료구조인 딕셔너리 를 택했다.
이로 인해 find 함수와 union 함수의 구조도 약간의 수정을 가해야 했다.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline

def find(x):
    if friend[x] != x:
        friend[x] = find(friend[x])
    return friend[x]

def union(a, b):
    a, b = find(a), find(b)
    if a == b:
        return
    friend[b] = a


for _ in range(int(read())):
    friend = dict()
    for _ in range(int(read())):
        a, b = read().split()
        if a not in friend:
            friend[a] = a
        if b not in friend:
            friend[b] = b
        root_a, root_b = find(a), find(b)
        union(a, b)
        root_list = list(friend.values())
        print(root_list.count(root_a) + root_list.count(root_b))

탐색 방식은 나쁘지 않았으나, 수량을 구하는 과정이 문제였다.

내가 처음으로 풀이한 방식은 아래와 같았다.

각 인원이 소속된 트리의 루트 노드를 담는 변수 friend 를 만든다.
만약 새로운 인원이 친구 관계를 맺었다면, 이를 friend 에 추가한다.
기존에 등록된 두 인원이 친구 관계를 맺는다면, union 을 실행한다.
3-1. union 작업은 나중에 입력된 유저가 앞선 유저의 집합에 속하도록 한다.
이후, 병합 이전에 각 유저가 소속된 집합의 크기를 구하고, 이를 더해 출력한다.

테스트 케이스에서는 문제 없이 결과가 잘 나왔지만, 시간 초과가 나오고 말았다.

원인은 두 사람이 소속된 집합의 크기를 구하는 과정에서 쓰인 count 함수였다.
그리고 두 사람이 애당초 같은 집합에 소속되었는지도 체크하지 않은 게 문제였다.

✅ Correct Code

import sys

read = sys.stdin.readline

def find(x):
    if friend[x] != x:
        friend[x] = find(friend[x])
    return friend[x]

def union(a, b):
    a, b = find(a), find(b)
    # 같은 집합에 소속되었다면, 굳이 병합을 진행하지 않아도 무방함.
    if a == b:
        return
    # b 집합을 a 집합에 포함시킨다.
    friend[b] = a
    # b 집합이 a 집합에 포함될 경우, b 집합에 소속되어 있던 원소의 수량도 더해야 한다.
    participants[a] += participants[b]


for _ in range(int(read())):
    friend = dict() # 참여자가 소속된 트리의 루트 노드를 담는 딕셔너리
    participants = dict() # 참여자를 루트 노드라고 가정했을 때, 하위에 놓인 노드의 수량
    for _ in range(int(read())):
        a, b = read().split()
        if a not in friend:
            friend[a] = a
            participants[a] = 1
        if b not in friend:
            friend[b] = b
            participants[b] = 1
        union(a, b)
        # a 집합이 b 집합을 포함 시키므로, 무조건 a 집합에 할당된 노드의 수를 구해야 함.
        print(participants[find(a)])