백준 4195번 - 친구 네트워크

친구 네트워크 문제 바로 가기

풀이 날짜: 2026-04-09

baekjoon 알고리즘 문제 풀이

풀이 코드


t = int(input())
for _ in range(t):
    f = int(input())

    parent = {}
    size = {}

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

    def union(parent,a,b):
        a = find_parent(parent,a)
        b = find_parent(parent,b)
        if a != b:
            if a < b:
                parent[b] = a
                size[a] += size[b]
                return size[a]
            else:
                parent[a] = b
                size[b] += size[a]
                return size[b]
        return size[a]
        
    for _ in range(f):
        a,b = input().split()
        
        if a not in parent:
            parent[a] = a
            size[a] = 1

        if b not in parent:
            parent[b] = b
            size[b] = 1

        print(union(parent,a,b))

문제 이해

이 문제는 친구 관계가 주어질 때마다 현재 형성된 친구 네트워크의 크기를 출력하는 문제이다. 입력으로 여러 개의 친구 관계가 순서대로 주어지며, 두 사람이 친구가 되면 각각이 속한 친구 네트워크가 하나로 합쳐지게 된다. 예를 들어 Fred Barney가 친구가 되면 두 사람은 하나의 네트워크에 속하게 되고, 이후 Barney Betty가 친구가 되면 Fred, Barney, Betty 세 사람이 모두 같은 네트워크가 된다. 중요한 점은 친구 관계가 입력될 때마다 현재 두 사람이 속한 네트워크의 전체 인원 수를 즉시 출력해야 한다는 것이다.

또 하나의 특징은 사람을 나타내는 값이 숫자가 아니라 문자열 이름이라는 점이다. 따라서 일반적인 배열 기반 그래프 구조 대신 이름을 키로 사용하는 딕셔너리를 활용해야 한다.

접근 방법

이 문제는 Union-Find(Disjoint Set) 자료구조를 활용하면 효율적으로 해결할 수 있다. Union-Find는 서로 다른 집합을 합치거나 같은 집합에 속해 있는지를 빠르게 확인할 수 있는 자료구조이다. 친구 관계를 하나의 연결 관계라고 보면, 친구 관계가 추가될 때마다 두 사람의 집합을 합치는 방식으로 문제를 해결할 수 있다.

Union-Find의 핵심 연산은 두 가지이다. 첫 번째는 find 연산으로, 특정 원소가 속한 집합의 대표(루트)를 찾는 연산이다. 두 번째는 union 연산으로, 서로 다른 두 집합을 하나로 합치는 연산이다. 이 문제에서는 두 사람이 속한 집합을 합친 뒤, 그 집합의 크기를 출력해야 하므로 집합의 크기를 따로 관리해야 한다.

자료구조 설계

이 문제에서는 사람의 이름이 문자열로 주어지기 때문에 배열 대신 딕셔너리를 사용한다. parent 딕셔너리는 각 사람의 부모 노드를 저장하며, 초기에는 자기 자신을 부모로 갖는다. 즉, 새로운 사람이 등장하면 parent[name] = name으로 초기화한다. 또한 size 딕셔너리를 사용해 각 집합의 크기를 저장한다. 처음 등장한 사람은 친구가 없는 상태이므로 네트워크 크기는 1이 된다.

핵심 아이디어

친구 관계 (a, b)가 입력될 때마다 다음 과정을 수행한다. 먼저 find 연산을 통해 두 사람이 속한 집합의 루트를 찾는다. 만약 두 루트가 서로 다르다면 두 집합을 합친다. 집합을 합칠 때는 한쪽 루트를 다른 쪽의 부모로 설정하고, 루트 노드의 size 값을 두 집합의 크기의 합으로 업데이트한다. 이렇게 하면 두 네트워크가 하나의 네트워크로 합쳐진다.

만약 두 사람이 이미 같은 집합에 속해 있다면 이미 같은 친구 네트워크이므로 집합을 합칠 필요는 없다. 이 경우에도 현재 네트워크의 크기를 그대로 출력하면 된다.

회고

이 문제를 통해 Union-Find 자료구조를 단순히 집합을 합치는 용도뿐 아니라 네트워크 크기를 관리하는 문제에도 활용할 수 있다는 점을 이해할 수 있었다. 또한 일반적인 Union-Find 문제와 달리 노드가 숫자가 아니라 문자열로 주어질 수 있기 때문에 딕셔너리를 활용한 구현 방법도 익힐 수 있었다. 이러한 패턴은 친구 관계, 네트워크 연결, 그룹 형성 문제 등 다양한 그래프 문제에서 자주 등장하기 때문에 기억해 두면 이후 문제 해결에 큰 도움이 될 것 같다.

Vienna sausage