민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
입력에 따라 네트워크를 계속해서 이어나가야 합니다. 또한 네트워크 내부에 몇 명이 있는지 지속적으로 알아야 합니다.
그래프 탐색으로 생각해봅시다. 네트워크를 구성하는것도 간단하고 BFS 혹은 DFS로 네트워크에 몇 명이 있는지 찾을 수 있습니다. 하지만 입력 조건을 보니 친구의 관계 수가 100,000 일 수 있습니다. 즉, 네트워크 인원을 세기 위해서 매번 탐색하게 되면 시간초과를 보게 될 것입니다.
생각을 그래프에서 집합으로 전환해 봅시다. 연결된 집합을 관리하기 위한 자료구조인 분리집합(disjoint set)을 떠올릴 수 있습니다.
부모를 기준으로 네트워크애 연결된 인원 수를 저장하고, 새롭게 이어줄 때(Union) 부모 위치만 사용하게 되므로 매번 탐색할 필요가 없기 때문에 문제의 요건을 충족시킬 수 있습니다!
⚠️주의할 점⚠️
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class FriendNetwork {
static int index;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(br.readLine());
for (int i = 0; i < testCase; i++) {
index = -1;
networking(sb, br);
}
System.out.println(sb);
br.close();
}
public static void networking(StringBuilder sb, BufferedReader br) throws IOException {
int f = Integer.parseInt(br.readLine());
HashMap<Integer, Integer> networkMemNumberMap = new HashMap<>(); // 네트워크 내부의 인원들을 담은 맵
HashMap<String, Integer> nameIndexMap = new HashMap<>(); // 이름 to 배열 index
int[] disjointSet = new int[f * 2];
// disjointSet init
for (int i = 0; i < f * 2; i++) {
disjointSet[i] = i;
networkMemNumberMap.put(i, 1);
}
for (int i = 0; i < f; i++) {
String[] input = br.readLine().split(" ");
int index1 = inputNameIndexMap(nameIndexMap, input[0]);
int index2 = inputNameIndexMap(nameIndexMap, input[1]);
sb.append(union(index1, index2, disjointSet, networkMemNumberMap)).append('\n');
}
}
public static int union(int i1, int i2, int[] disjointSet, Map<Integer, Integer> networkMemNumberMap) {
i1 = find(i1, disjointSet);
i2 = find(i2, disjointSet);
if (i1 != i2) {
int parent = Math.min(i1, i2);
int child = Math.max(i1, i2);
disjointSet[child] = parent;
networkMemNumberMap.put(parent, networkMemNumberMap.get(parent) + networkMemNumberMap.get(child));
networkMemNumberMap.remove(child);
return networkMemNumberMap.get(parent);
}
return networkMemNumberMap.get(i1);
}
public static int find(int start, int[] disjointSet) {
if (disjointSet[start] != start) {
return disjointSet[start] = find(disjointSet[start], disjointSet);
}
return start;
}
public static int inputNameIndexMap(Map<String, Integer> map, String name) {
if (!map.containsKey(name)) {
map.put(name, ++index);
}
return map.get(name);
}
}