[백준] Python - 친구 네트워크

4195번: 친구 네트워크

 

Union-Find를 사용하는 분리집합 문제이다.

 

항상 보면 BFS/DFS 같은 문제나 분리 집합 문제들은 기본적인 형태가 유사한 것 같다.

다만 이 문제는 한가지 고려 사항이 있다.

 

친구 관계가 입력으로 주어지는데 이 친구들의 이름이 문자열로 입력된다.

여기서 나는 두 가지를 고려했다.

 1. 부모 노드를 배열이 아닌 딕셔너리로 저장할 것

 2. 이름을 정수로 매핑할 딕셔너리를 새로 생성할 것

 

부모 노드를 문자열 딕셔너리를 통해서만 확인하면 시간초과가 나온다...

그래서 이름을 정수로 매핑해서 그 친구 관계 숫자를 바로바로 확인할 수 있게 구현하였다. 

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음