iamyoungbin

You’ll never forget my name

최대 1 분 소요

Problem

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

Idea

사용자를 정점으로 친구 관계를 간선으로 생각하면 친구 관계가 주어질 때마다 두 사용자가 속한 트리에 포함된 정점이 몇 개인지 제시해야 한다.

Union-Find를 이용해 rank 배열에 트리에 속한 정점의 수를 저장하는 것으로 풀었다.

Code

import sys

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

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

    if x != y:
        if rank[x] >= rank[y]:
            parent[y] = x
            rank[x] += rank[y]
            print(rank[x])
        else:
            parent[x] = y
            rank[y] += rank[x]
            print(rank[y])
    else:
        print(rank[x])

t = int(input())
for _ in range(t):
    F = int(input())
    rank = {}
    parent = {}

    for _ in range(F):
        x, y = sys.stdin.readline().split()
        if x not in parent:
            parent[x] = x
            rank[x] = 1
        if y not in parent:
            parent[y] = y
            rank[y] = 1

        union(x, y)

Comment

문제를 풀고나서 다른 해결방법이 있나 찾아보던 도중 기존의 방식에서 조금 더 개선된 Weight Union-Find라는 방식이 있다는 것을 알게 되었다. 기존 Union-Find에서는 부모 정보를 저장하는 배열과 트리의 사이즈를 저장하는 배열을 따로 두는 것과 달리 개선된 방식에서는 두 정보를 하나의 배열에 저장해 메모리 공간을 절반으로 절약할 수 있다. Weight Union-Find 방식에서는 기본적으로 부모 정보를 저장하되 자신이 루트 노드일 경우 -(트리의 사이즈)를 저장한다.

참고