[알고리즘] 백준4195 친구 네트워크 - 파이썬

단계별 풀기의 유니온 파인드 세 번째 문제이다. 전에 풀었던 두 문제와 달리 배열을 예제 입력 시에 해줘야 된다는 점이었다. find함수와 union함수도 좀 다르게 구현했어야 했다. (결국 다른 분의 블로그를 보고..ㅜ)

 

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

4195번: 친구 네트워크

 

 

[풀이 코드]

from sys import stdin

input = stdin.readline

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


def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a
        number[a] += number[b]
    print(number[a])


for _ in range(int(input())):
    num = int(input())
    parent, number = {}, {}
    for i in range(num):
        a, b = input().split()
        if a not in parent:
            parent[a] = a
            number[a] = 1
        if b not in parent:
            parent[b] =b
            number[b] = 1
        union(a, b)

 

 

- parent와 number함수를 입력을 받은 뒤에 초기화 해준다는 점에서 전에 풀었던 문제와 다른 것을 알 수 있다. 또 union 또한 조금 다른 형식이다. 하지만 알고리즘은 같고 연습이 아직 많이 필요한 것 같다.

 

[참고 블로그]

두개의 딕셔너리를 써서 해결하셨는데 어떻게 이런 생각을 했는지.. 난 조금 더 쉽게 생각하는 습관이 필요한 것 같다. 

https://chancoding.tistory.com/50

[Python] 백준 4195번 친구 네트워크 - 유니온 파인드(Union Find) 활용