[Python - Data Structure, Map] 4195 - 친구 네트워크

📌 문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

 

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

📌 입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

📌 출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

📌 문제 풀이

👨‍🏫 접근

친구 네트워크는 서로 분리된 집합으로 존재하기 때문에 합치기 연산으로 각 집합을 구별해주어야 한다.

 

이때 중요한 것은 그 집합에 몇 명의 사람이 있는지 찾아내는 것이다.

집합 연산 알고리즘에서 사용하는 부모 테이블에서 집합 원소의 개수를 함께 2차원 리스트로 담아주어서 활용했다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def human_to_num(human):
    global cnt
    if human not in number:
        number[human] = cnt
        parent.append([cnt, 1])
        cnt += 1
    return number[human]


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


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b][0] = a
        parent[a][1] += parent[b][1]
    else:
        parent[a][0] = b
        parent[b][1] += parent[a][1]


t = int(input())

for _ in range(t):
    f = int(input())
    number = {}
    cnt = 0
    parent = []
    for i in range(f):
        a, b = map(human_to_num, input().rstrip().split())
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
        k = find_parent(parent, a)
        print(parent[k][1])

📄 준비

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def human_to_num(human):
    global cnt
    if human not in number:
        number[human] = cnt
        parent.append([cnt, 1])
        cnt += 1
    return number[human]


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


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b][0] = a
        parent[a][1] += parent[b][1]
    else:
        parent[a][0] = b
        parent[b][1] += parent[a][1]
        
t = int(input())

세 가지 함수를 사용한다. 첫 번째는 각 사람의 이름을 정수로 나타내주는 연산이며, 두 번째는 조상을 찾는 연산, 세 번째는 두 집합을 합쳐주는 연산이다.

 

핵심은 합치기 연산에서 집합의 원소 개수를 더해주는 것이다.

📄 풀이

for _ in range(t):
    f = int(input())
    number = {}
    cnt = 0
    parent = []
    for i in range(f):
        a, b = map(human_to_num, input().rstrip().split())
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
        k = find_parent(parent, a)
        print(parent[k][1])

이때, 두 친구의 조상이 겹치는 경우인 사이클이 발생할 경우에는 합치기 연산 없이 값을 출력해준다. 사이클인데도 합치기 연산을 하면 값이 두 배로 불어나기 때문에 오류가 발생한다.

📌 총평

합치기 연산을 이렇게도 응용할 수 있구나를 알 수 있어 좋았다.