📕문제

[Baekjoon] 4195. 친구 네트워크

문제 설명

Fred, Barney, Barney, Betty 와 같이 새로운 친구 관계가 주어질 때마다 해당 친구 네트워크에 존재하는 인원 수를 출력하는 문제다.
친구의 친구와 같이 관계를 따라갔을 때 연결되어 있으면 같은 친구 네트워크에 존재한다고 볼 수 있다.

---

📝풀이

import sys

read = sys.stdin.readline

N = int(read())

class DisjointSet:
    def __init__(self):
        self.parent = {}
        self.size = {}

    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1
            
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.size[rootX] < self.size[rootY]:
                self.parent[rootX] = rootY
                self.size[rootY] += self.size[rootX]
            else:
                self.parent[rootY] = rootX
                self.size[rootX] += self.size[rootY]

        return self.size[self.find(x)]




for _ in range(N):
    F = int(read())
    ds = DisjointSet()

    for _ in range(F):
        x, y = map(str, read().split())
        ds.add(x), ds.add(y)
        print((ds.union(x, y)))

• DisjointSet: 친구 네트워크를 구분하기 위한 분리집합.
  • __init__: 분리집합의 생성자.
    자신이 소속한 친구 네트워크의 대표 친구를 저장하기 위한 딕셔너리(key: 본인, value: 대표 친구)와
    각 친구 네트워크의 인원 수를 저장하기 위한 딕셔너리(key: 대표 친구, value: 인원 수)
  • add: 친구를 자료구조에 등록하는 함수.
  • find: x가 속한 친구 네트워크의 대표 친구를 찾는 함수.
  • union: x와 y가 속한 친구 네트워크를 합치는 함수.
    두 사람이 속한 친구 네트워크가 같지 않은 경우 실행된다.
    두 친구 네트워크 중 인원이 적은 네트워크가 큰 네트워크로 합쳐진다.(find의 경로 수정을 최소화 하기 위함)