[파이썬][백준] 4195번: 친구 네트워크

1. 문제

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

4195번: 친구 네트워크

문제 유형: 해시, 집합, 그래프

 

풀이

 

가정: 'A'와 'B'가 친구이고 'B'와 'C'가 친구일 때

'B'와 'C'의 친구 네트워크 내의 사람 수는 3명이다.

'A'를 'B'의 parent node로 두고 'B'를 'C'의 parent node로 둔 다음에 두 parent node를 이어준다. 이것을 이용하여 코드를 작성하였다.

 

1. 두 사람을 입력받았을 때 parent_node에 두 사람이 있는지 확인

    - parent_node에 없을 경우 초기화

    - parent node를 본인으로 입력, 네트워크의 수를 1로 입력

2. union 함수 실행

    - 두 사람의 최상위 parent node를 찾아주는 find 함수 실행

    - 두 사람의 최상위 부모 노드를 연결한 후 네트워크의 개수 출력

 

2. 소스코드

# 자기 자신을 부모 노드로 두고 네트워크내 사람 수를 1로 초기화
def initialize(person):
    parent_node[person] = person
    number[person] = 1

# 해당 사람의 최상위 parent node 탐색
def find(person):
    if person == parent_node[person]:
        return person
    else:
        temp = find(parent_node[person])
        parent_node[person] = temp
        return parent_node[person]

# 두 최상위 parent node를 비교하여 다르면 연결
def union(person_a, person_b):
    person_a = find(person_a)
    person_b = find(person_b)

    if person_a != person_b:
        parent_node[person_b] = person_a
        number[person_a] += number[person_b]


testcase = int(input())

for _ in range(testcase):
    # 해당 사람과 parent node, 수를 입력하기 위해 dict()로 선언
    parent_node = dict()
    number = dict()

    f = int(input())

    for _ in range(f):
        person_a, person_b = input().split()

        if person_a not in parent_node:
            initialize(person_a)
        if person_b not in parent_node:
            initialize(person_b)

        union(person_a, person_b)
        print(number[find(person_a)])