[BOJ_Python] 4195. 친구 네트워크

문제

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

 

사용 알고리즘

Union-Find

 

풀이

고려사항

1. 친구 리스트에 존재 여부

2. 친구 연결

 

후기

1. 이 문제의 keypoint는 union-find를 딕셔너리를 통해 진행하는 것이다.

보통은 숫자로 진행했지만, 이 문제의 경우 문자열로 받기 때문에 딕셔너리를 통해 진행했다.

 

2. 우선 친구 딕셔너리(parents)에 존재 여부를 확인 후 존재하지 않는다면

root를 자신으로 친구 딕셔너리에 등록, size 딕셔너리에 1로 세팅한다.

 

3. 이후 기존 union-find 알고리즘을 진행한다.

- 현재 분리 집합의 root를 find 함수를 통해 구해준 후

- 서로 같은 집합이 아닐 경우 union을 통해 서로 분리 집합을 합쳐준다.

4. 이때 실시간으로 분리집합의 크기를 출력한다.

- 분리 집합의 크기 출력 시 합쳐진 크기를 출력해야하며, 

- 이미 같은 집합에 속한 친구의 경우 그 크기를 출력한다.

 

코드

import sys
input = sys.stdin.readline


def find_set(x):
    if parents[x] != x:
        parents[x] = find_set(parents[x])
    return parents[x]


def union(x, y):
    x, y = find_set(x), find_set(y)

    if x == y:
        # 이미 같은 집합인 경우에는 size가 큰 것을 찾아 출력
        print(max(size[x], size[y]))
        return

    if size[x] < size[y]:
        parents[x] = y
        size[y] += size[x]
        print(size[y])
    else:
        parents[y] = x
        size[x] += size[y]
        print(size[x])


T = int(input())

for tc in range(T):

    N = int(input())
    parents = {}
    size = {}

    for network in range(N):
        friends = list(input().split())
        # 새로운 친구인 경우 초기 세팅 필요
        for friend in friends:
            if friend not in parents:
                parents[friend] = friend
                size[friend] = 1
        # 입력 받은 친구 2명끼리 union 진행
        union(friends[0], friends[1])

 

결과