난이도 : 골드 2
유형 : 유니온 파인드
https://www.acmicpc.net/status?user_id=alswns8495&problem_id=1976&from_mine=1
문제
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다.
다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
예시를 보자
첫 줄에 테스트 케이스의 개수 , 2
그 아래에 친구 관계의 수 F
그 아래에 사용자의 아이디 한 쌍씩 F줄 입력받는다.
Fred Barney 를 받았을 때, 친구 네트워크에 몇 명이 있는지는
이렇게 그래프가 형성되고 친구 네트워크에 2명이 있어서 2가 출력된다.
그 아래에 Betty가 Barney와 연결되면,
친구 네트워크에 Betty가 추가되어 3이 출력된다.
마지막 Wilma가 추가되면 그려볼것도 없이 4가 출력된다.
즉 친구네트워크에 속하게하는 Union 연산과 같은 집합에 속하는 지 확인하는 Find 연산으로 해결하는 유니온 파인드 문제이다.
유니온 파인드 함수를 구현하고 친구 한 쌍을 유니온해준뒤 그 유니온 해준 집합의 원소의 개수를 출력해주면 된다.
항상 parent에 숫자로 받다가 문자열로 받는 것이 문제였다.
해결 아이디어
기존의 유니온 파인드는 숫자 기반(노드 번호)로 작동하지만, 이 문제는 사용자 ID가 문자열이다. 따라서 문자열 ID를 숫자로 매핑해주는 작업이 필요하다.
또한 단순히 두 노드를 같은 집합으로 묶는 것뿐만 아니라, 해당 집합의 크기도 계속 추적해야 하므로, parent 배열 외에 size 배열도 함께 관리한다.
해답 및 풀이
import sys
input = sys.stdin.readline
def find(x):
if parent[x] != x:
parent[x]= find(parent[x])
return parent[x]
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x != root_y:
parent[root_y] = root_x
size[root_x] += size[root_y]
return size[root_x] # 유니온 함수에 리턴값에 합쳐진 집합의 크기를 리턴해주는게 핵심 포인트
T = int(input())
for _ in range(T):
F = int(input())
parent = dict() # dict 로 구현
size = dict()
for _ in range(F):
a, b = input().split()
# 처음 보는 사람이라면 초기화
if a not in parent:
parent[a] = a
size[a] = 1
if b not in parent:
parent[b] = b
size[b] = 1
# 유니온 하고 크기 출력 ( union 함수의 리턴값을 size로 정의해놨으니까 )
print(union(a, b))parent 배열을 사용자의 ID가 문자열이어서 dict로 구현한 것과
각 집합(친구 네트워크)의 크기를 추적해야 했기에 size 배열을 정의 한 것,
마지막으로 union 함수에 return 값에 size 배열의 값을 반환하도록 한 것이 킥이었다.
++ 언제 dict를 떠올려야 할까?
자주 등장하는 상황 5가지
- 문자열을 인덱스처럼 써야 할 때
- 특정 정보(값)를 빠르게 저장하고 찾고 싶을 때
- 데이터에 규칙이 없을 때, 순서보다 ‘매핑’이 중요할 때
- 중복 없이 빠르게 검색하고 싶을 때
- 카운팅(등장 횟수 세기)
# 유니온 파인드 / 이름이 인덱스 역할을 해야 할 때
parent = dict()
parent["Alice"] = "Alice"