[백준] 4195번 친구 네트워크 자바

문제

 

4195번: 친구 네트워크

 

 

문제 풀이

 

HashMap을 이용하여 친구의 이름을 숫자로 표현해야 배열 인덱스를 이용할 수 있다. 그리고 union-find함수를 이용하여 두 친구 관계의 집합 크기를 늘려간다.

이때 연결 노드를 저장할 부모 배열외에 몇개가 연결되어있는지 누적하기 위해 count 정수형 배열을 하나 더 사용해준다.

count배열에는 처음에 모두 1로 초기화해주고 해당 원소가 다른 원소로 합쳐질 때(부모값이 변경될 때) count값을 해당 원소의 최상위 부모 count배열에 더해준다. 이렇게 친구 관계가 늘어날 경우 합쳐진 최상위 부모 노드의 count배열에 값을 누적해서 저장해 준 후 출력해준다. 어려웠던 문제였다.

 

 

소스 코드

 

public class b_4195 {

	static int[] parent;
	static int[] count;
	static HashMap<String, Integer> map;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		
		for(int i = 0; i < testcase; i++) {
			int F = sc.nextInt();	//친구 관계 수
			int idx = 1;
			parent = new int[200001];
			count = new int[200001];
			map = new HashMap<>();
			
			Arrays.fill(count, 1);
			for(int a = 1; a <= 200000; a++)
				parent[a] = a;
			
			for(int j = 0; j < F; j++) {
				String s1 = sc.next();
				String s2 = sc.next();
				
				if(!map.containsKey(s1))
					map.put(s1, idx++);
				
				if(!map.containsKey(s2))
					map.put(s2, idx++);
				
				solution(s1, s2);
			}
		}
		
		sc.close();
	}
	
	public static void solution(String s1, String s2) {
		union(map.get(s1), map.get(s2));
		System.out.println( count[find(map.get(s1))] );
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y)	return;
		else if(x < y) {
			parent[y] = x;
			count[x] += count[y];
		}
        	else {
        		parent[x] = y;
        		count[y] += count[x];
        	}
	}
	
	public static int find(int x) {
		if(parent[x] == x)
			return x;
		
		return parent[x] = find(parent[x]);	
	}
}