[BAEKJOON] 4915. 친구 네트워크

문제 출처 : https://www.acmicpc.net/problem/4195

 

사용한 알고리즘

• Union find 문제 -> disjoint set 알고리즘 [ https://gayoung78.tistory.com/75 알고리즘 설명] 

 

풀이 로직

• 친구 네트워크의 숫자를 위해 하나의 거대한 union network의 parent에 몇명의 친구가 있는지 저장하는 number 딕셔너리를 정의

1. 두 사람의 이름을 입력받은 후, 딕셔너리 parents에 없는 이름이라면 추가해준다.

2. 두 이름을 합쳐 친구관계를 만든다.

3. 현재까지 해당 친구관계를 포함하여 같은 집합에 있는 원소의 개수를 출력한다.

 

코드

• getParent
  • parents 딕셔너리를 참조해 부모노드를 알 수 있다.
  • 입력받는 노드가 부모노드이면 그대로 반환하지만, 그렇지 않으면 재귀를 이용해 부모노드를 찾는다.
• unionParent
  • 두 노드를 합치는 역할
  • 두 노드가 속한 집합의 부모노드를 찾아 비교. 부모노드를 갖지 않으면 x를 기준으로 두 집합을 합친다.(cnt+=1)
• findParent
  • 입력받은 노드의 루트 노드를 찾는다. 

 

어려운 점

• sys를 이용해 input을 받지 않으면 하지 않으면 5836초, sys를 이용해 input을 받으면 340 (시간 차이가 많이난다.)
• disjoint-set 알고리즘을 알기 전에는 친구 관계를 다 정의한 딕셔너리를 만든 후, 친구의 노드로 가 계속 명수를 추가하려했다. 하지만, 재귀를 이용해서 풀지만, 제대로 구현이 안되었고, 알고리즘을 공부했다.