[백준]4195 친구 네트워크(Python)

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

4195번: 친구 네트워크

 

문제 접근

 

문제 이해가 먼저 

친구 이름으로 (x, y)를 입력 받는다고 하면 x ← y로 부모 ← 자식 관계 형성

1. Fred ← Barney (2)

2. Barney ← Betty       Fred ← Barney ← Betty (3)

3. Betty ← Wilma       Fred ← Barney ← Betty ← Wilma (4) 

 

코드

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a == b :
        return network[a]   # a,b가 이미 같은 집합에 속해있다면, 현재 집합의 크기 그대로 반환
    parents[b] = a
    network[a] = network[a] + network[b]
    return network[a]   # 합쳐진 네트워크 크기 반환

for _ in range(int(input())):
    parents = dict()    # 각 노드의 루트 노드(부모)를 저장할 공간
    network = dict()    # 각 네트워크의 크기를 저장할 공간

    for _ in range(int(input())):
        a, b = input().rstrip().split()
        # 처음 등장한 노드의 경우, 각각을 루트 노드로 설정하고 네트워크 크기를 1로 설정
        if parents.get(a) == None:
            parents[a] = a
            network[a] = 1
        if parents.get(b) == None:
            parents[b] = b
            network[b] = 1

        # a, b 노드를 합치고, 합쳐진 네트워크 크기 출력
        print(union_parent(a,b))

 

문제 회고 

 

딕셔너리를 사용한다는 점이 생소했고, 합집합 연산 함수의 경우 약간의 커스텀이 필요했다. 

그리고 저 a == b의 조건문이 매우 중요한 것 같다. 

 

코드를 시각화해주는 툴 살포시 추천...합니다~~!!

https://pythontutor.com/render.html#mode=display

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java