[백준] 4195 친구 네트워크

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

친구 관계가 주어지면 두 이름은 하나의 친구가 되어 같은 그룹에 속하게 됩니다.

친구 관계가 주어질때 마다 해당 그룹에 속한 인원 수를 출력해야 했습니다.

 

그룹을 계속해서 생성하거나 하나로 합치는 과정이 필요했습니다.

이 부분을 서로소집합과 연관지어 접근하였습니다.

 

기존의 간단한 서로소 집합은 1차원 배열을 이용하여 그룹들을 합치는 과정을 통해 특정 수들이 서로 같은 그룹에 속했는지 여부를 판별할 수 있습니다.

이를 참고하여 이름별 속한 그룹의 번호를 명시하는 딕셔너리 변수와 그룹별 속한 이름의 명단을 기록하는 1차원 배열을 이용하였습니다.

 

친구 관계가 주어질때 마다 주어진 이름이 현재 그룹에 속해있는지 여부와 그룹의 조건들을 비교하여 그룹을 변경하는 과정을 거쳤습니다. 

2) 알고리즘

• 자료구조
• 서로소집합

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')


# from 그룹원들의 번호를 to 그룹으로 변경
def move_group(to_group, from_group):
    for e in group[from_group]:
        friends[e] = to_group


T = int(sys.stdin.readline())

for _ in range(T):
    F = int(sys.stdin.readline())

    # 이름별 속한 그룹 번호
    friends = {}
    # 그룹별 속한 이름의 명단
    group = [set() for _ in range(F+1)]

    for i in range(1, F+1):
        a, b = sys.stdin.readline().split()

        # 이번에 처음 나온 친구 관계인 경우
        # 새롭게 등록
        if not friends.get(a, False) and not friends.get(b, False):
            friends[a], friends[b] = i, i
            group[i] = set((a, b))
        # 둘 다 이미 친구 그룹에 속해있는 경우
        elif friends.get(a, False) and friends.get(b, False):
            # 서로 다른 그룹일때만, 두개의 그룹을 합침
            if friends[a] != friends[b]:
                to_group, from_group = friends[a], friends[b]
                group[to_group].update(group[from_group])
                move_group(to_group, from_group)
                group[from_group].clear()
        # 둘 중 하나만 그룹에 속한 경우, 존재하는 그룹으로 귀속
        else:
            group_number = friends.get(a, False) or friends.get(b, False)
            friends[a], friends[b] = group_number, group_number
            group[group_number].update([a, b])

        print(len(group[friends[a]]))

---

🔗 문제 링크

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

4195번: 친구 네트워크

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다