![[4195번] 친구 네트워크](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnC7Df%2Fbtqw5fM17Wt%2F9UomcqmDe9mO22sF7Kd49K%2Fimg.png)
4195번: 친구 네트워크
문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계
www.acmicpc.net
이전 포스팅에서 다뤘던 '유니온 파인드'에 대한 변형 문제입니다.
이번에는 각 유니온들의 root 노드들이 기존 배열에서 정수로 된 index를 이용하는 것이 아니라 "String"을 이용하는 점에 주목해야 합니다.
나타날 수 있는 이름의 개수는 최대 200,000명으로, 이를 index로 이용하려 합니다.
생각해보면 이름이 다 다르게 주어졌다는 가정 하에 Search를 수행해보겠습니다.
Linear Search의 시간 복잡도가 $O(N)$인 만큼 단순 탐색으로는 시간 초과가 돼도 한참 된다는 것을 알 수 있습니다.
저는 그래서 이름과 값을 저장할 수 있으면서 동시에 Binary Search(시간 복잡도: $O(\log_2 N)$)를 사용할 수 있는 Container를 떠올렸습니다.
바로 이전 포스팅들에서도 사용해왔던 'map' Container입니다.
map Container는 BST 구조를 띄도록 설계되어 있고, 자료형도 자유롭게 쓸 수 있으므로 이 문제를 위한 딱 맞는 Container였죠.
그래서 저는 인자로 <string, pair<stirng, int> >를 사용했습니다.
- 첫 번째 string ☞ Binary Search로 찾을 root 값.
- 두 번째 string ☞ 입력 시 주어졌던 친구의 이름; 연결되어 있다면 이리로 넘어가기 위한 index로 사용하기 위함!
- 세 번째 int ☞ root 노드는 '두 번째 string'의 값이 빈 칸으로 되어 있다. 이때 연결된 친구들의 총인원수를 저장해둠.
이렇게 모든 입력을 처리하고 각 쿼리에 대해 답을 출력해 주었습니다.
여러분도 Search가 오래 걸릴 것 같은 문제가 있을 때에는 항상 시간 복잡도가 $\log$가 되도록 만들어보도록 합시다.
<여담>
문제를 맞히고 나서 다른 분들의 소스를 보았습니다. 저는 위에서 보셨다시피 '세 번째 int'를 통해서 root만 그 수를 이용하도록 했는데
다른 분들은 map의 인자로 <string, int>로만 해놓으시고 int는 다른 int 배열의 index값을 참조하도록 했더군요.
그런 최적화 방식을 생각하신 분들이 참 대단하다고 생각되었습니다...
그래서 저는 좀 오래 걸린 소스였죠 ㅠㅠ