백준_4195_친구네트워크

백준

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;
		}
		
		
	}
	

	
	
}