새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 4195 친구 네트워크

by 언호 2022. 8. 18.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

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

댓글