민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
2
3
4
2
2
4
이 문제는 find-union 알고리즘을 이용해서 풀 수 있었다. 처음에는 HashMap을 이용해서 idx를 계산한 뒤에 배열을 통해 find-union 알고리즘을 적용하는 방법을 이용했으나 시간이 오래 걸렸다. 다른 풀이는 HashMap을 이용해서 이름 String을 그대로 저장해서 find-union 알고리즘을 적용하는 방법이다.
import java.io.BufferedReader; //1번 방법
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
static int[] parent;
static int[] cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
int F = Integer.parseInt(br.readLine());
HashMap<String, Integer> map = new HashMap<>();
cnt = new int[2*F]; //F개의 관계가 모두 다른 사람일 경우의 최대 배열 크기 2*
parent = new int[2*F];
for(int j=0; j<cnt.length; j++) {
parent[j] = j;
cnt[j] = 1;
}
int idx = 0;
for(int j=0; j<F; j++) {
String[] input = br.readLine().split(" ");
String a = input[0];
String b = input[1];
int a_idx = 0;
int b_idx = 0;
if(!map.containsKey(a)) { //새로운 사람이름 등장할 때마다 idx++
map.put(a, idx);
a_idx = idx++;
}
else {
a_idx = map.get(a);
}
if(!map.containsKey(b)) {
map.put(b, idx);
b_idx = idx++;
}
else {
b_idx = map.get(b);
}
union(a_idx, b_idx);
sb.append(cnt[find(a_idx)]).append("\n");
}
}
System.out.println(sb.toString());
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a!=b) {
if(a<b)
parent[b] = a;
else
parent[a] = b;
int x = cnt[a];
cnt[a] += cnt[b];
cnt[b] += x;
}
}
public static int find(int a) {
if(parent[a]==a)
return a;
return parent[a] = find(parent[a]);
}
}
import java.io.BufferedReader; //2번
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
static HashMap<String, String> parent;
static HashMap<String, Integer> cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
cnt = new HashMap<>();
parent = new HashMap<>();
for(int i=0; i<T; i++) {
int F = Integer.parseInt(br.readLine());
cnt.clear();
parent.clear();
for(int j=0; j<F; j++) {
String[] input = br.readLine().split(" ");
String a = input[0];
String b = input[1];
if(!parent.containsKey(a)) {
parent.put(a, a);
cnt.put(a, 1);
}
if(!parent.containsKey(b)) {
parent.put(b, b);
cnt.put(b, 1);
}
union(a, b);
sb.append(cnt.get(find(a))).append("\n");
}
}
System.out.println(sb.toString());
}
public static void union(String str1, String str2) {
str1 = find(str1);
str2 = find(str2);
if(!str1.equals(str2)) {
parent.put(str2, str1);
cnt.put(str1, cnt.get(str1)+cnt.get(str2));
}
}
public static String find(String str) {
if(parent.get(str).equals(str))
return str;
else {
String p = find(parent.get(str));
parent.put(str, p);
return find(parent.get(str));
}
}
}