문제
민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
풀이
test_case = int(input())
def find_parent(a):
if parent[a] == a:
return a
else:
p = find_parent(parent[a])
parent[a] = p
return p
def union(a, b):
parent_a = find_parent(a)
parent_b = find_parent(b)
if parent_a != parent_b:
parent[parent_b] = parent_a
number[parent_a] += number[parent_b]
for _ in range(test_case):
f = int(input())
parent = dict()
number = dict()
for _ in range(f):
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)
print(number[find_parent(a)])- 문제는 풀지 못 했다. 약 1시간 30분 정도 생각해보며 코드를 만들어 봤지만 결국엔 실패..
- 풀이 코드를 봐도 이해가 되지 않아 2시간 정도 계속해서 구글링 + 노트에 써가며 과정이 어떻게 진행되는 지 노력했다.
- Disjoint Set의 개념과 이를 구현할 알고리즘 Union-Find에 대해서 공부를 했다.
배운점
- Disjoin Set (서로소 집합, 분리집합) 개념
- Union-Find 알고리즘
다음 글로는 Disjoin Set, Union Find에 대해 글을 올려볼 생각이다.
또한 이 글 이후로, 새 알고리즘 풀이 글은 당분간 올리지 않을 것 같다.
여태껏 풀어온 문제들에 대하여 내가 이 문제들을 이해했는 지에 대해 복습해볼 생각이고,
그간 읽지 못 해서 메일에 쌓여있는 Javascript, Typescript, NodeJs, React Weekly Newletter를 읽어볼 계획이다. ( 해당 글에 대하여 번역본을 올릴 생각 )
하루 하루 조금씩 공부를 하지만 이러한 시간들이 쌓여 나에게 큰 영양분이 되길!!
