1. 문제 이해
문제를 읽어보면 각 줄에 친구 두명씩 주어지고 이둘은 서로 연결된다. 이와 같은 과정을 반복하면서 각단계에서 주어진 친구 두명을 포함하여 서로 연결된 총 친구의 명수를 출력하면된다.
예를 들어
A B => A, B 가 연결되고 이때 총 친구 네트워크는 2 이다.
B, C => B, C 가 연결되고 이때 총친구 네트 워크는 3이다. B는 A 와 연결되어있기 떄문!
2. 핵심 개념 (union find, hashMap)
Union Find 를 이용해서 풀이를 진행했다. 기존의 Union Find 는 a, b 의 노드를 합칠때 각 a, b 의 부모노를 찾고 부모노드의 값이 작은 것을 기준으로 합쳐줬다. 이문제에 응용 시켜보면 각 친구의 부모노드를 찾고(find) 하고 두 부모노드를 합쳐주면된다. 이떄 합쳐주는 기준을 정해주는것이 필요하다. 이때 각 부모노드의 자식수를 기준으로 합쳐준다.
예를 들어
a 의 부모노드는 c 였고 c 의 자식수는 4 이였다.!
b 의 부모노드는 d 였고 d 의 자식수는 6 이였다.!
=> 그러면 최종적으로 a, b 의 총 친구네트 워크 수는 10(4 + 6)이되고
d 의자식수가 더 크므로 c 의 부모노드를 d 로 바꿔준다.
기존의 union find 보다 각 노드의 자식수를 포함하는 변수가 필요하기 때문에 HashMap을 이용했다.
각 노드도 String 이기떄문에 자바에서는 String 을 배열의 Key 값으로 사용할 수 없기 때문에 HashMap 을 이용했다.
만약 Union Find 의 개념이 확실치 않다면 이 블로그를 추천합니다. https://m.blog.naver.com/ndb796/221230967614
3. 풀이
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class 친구네트워크 {
static HashMap<String, String> boss;
static HashMap<String, Integer> childNum;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
// 해쉬맵 두개선언.
// 하나는 String String A 의 보스를 담자
// 하나는 String, Integer 어떤 A 의 자식수(자기 포함)
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < t; i++) {
int f = sc.nextInt();
boss = new HashMap<String, String>();
childNum = new HashMap<String, Integer>();
for(int j = 0; j < f; j++) {
String f1 = sc.next();
String f2 = sc.next();
int res = union(f1, f2);
list.add(res);
}
}
for(int res : list) {
System.out.println(res);
}
}
static String find(String f1){
String res = boss.getOrDefault(f1, "");
return res == "" ? f1 : find(res);
}
static int union(String f1, String f2){
String a = find(f1); // 각친구의 최종 보스를 구하자!
String b = find(f2); // 각친구의 최종 보스를 구하자!
if(a.equals(b)) { // 이둘의 보스가 같을 경우에는 . 그 보스의 자식수를 리턴.
return childNum.get(a);
}
// 각각 연결이 안되있었던 경우
int num1 = childNum.getOrDefault(a, 1); // 처음인경우 1로 초기화!!
if(num1 == 1) childNum.put(a, 1);
int num2 = childNum.getOrDefault(b, 1); // 처음인 경우 1로 초기화!!
if(num2 == 1) childNum.put(b, 1);
if(num1 >= num2) { // 두 친구의 보스중의서 자식수가 더많은것을리턴!
childNum.put(a, num1 + num2); // 더작은 보스가 더큰 보스로 흡수됨!.
boss.put(b, a);
return num1 + num2;
}else {
childNum.put(b, num1 + num2);
boss.put(a, b);
return num1 + num2;
}
}
}
'백준' 카테고리의 다른 글
백준_8983_사냥꾼 (0) | 2020.12.25 |
---|