백준 4195 (친구 네트워크)

문제

---

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

 

 

 

 

풀이

---

친구가 몇명이 나올지 정확히 모르기 떄문에 임의의 숫자 100000로 배열을 받았다.

 

HashMap<String, Integer> 를 통해 이름(String) 값을 Key 로 하고, 노드 숫자(Integer) 값을 Value 로 사용하였다.

 

합집합 연산을 통해 친구 관계 수를 구해준다.

 

Union(합집합)연산은 다음과 같다.

public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	
	if(x != y) {
		if(x < y) {
			parent[y] = x;
			relation[x] += relation[y];
		}
		else {
			parent[x] = y;
			relation[y] += relation[x];
		}
	}
	else {
		return;
	}
 }

기존의 union 연산과 같지만 다른점은 relation 배열을 통해 크기를 저장해 놓는다.

 

부모의 노드번호가 더 작은 것으로 부모를 바꿔주면서 그때의 연결된 네트워크의 개수를 해당 부모의 relation 배열에 더해주어 크기를 저장해둔다.

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[] parent;
	static HashMap list;
	static int[] relation;
	static int idx;
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    //StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
	    
	    int n = Integer.parseInt(bufferedReader.readLine());
	    
	    for(int i = 0 ; i < n ; i++) {
	    	
	    	int f = Integer.parseInt(bufferedReader.readLine());
	    	
	    	idx = 0;
	    	list = new HashMap<String, Integer>();
	    	parent = new int[1000000];
	    	relation = new int[1000000];
	    	
	    	Arrays.fill(relation, 1);
	    	
	    	for(int j = 0 ; j < f ; j++) {
	    		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
	    		String friend1 = st.nextToken();
	    		String friend2 = st.nextToken();
	    		
	    		if(!list.containsKey(friend1)) {
	    			list.put(friend1, idx);
	    			parent[idx] = idx;
	    			idx++;
	    		}
	    		
	    		if(!list.containsKey(friend2)) {
	    			list.put(friend2, idx);
	    			parent[idx] = idx;
	    			idx++;
	    		}
	    		
	    		union((Integer)list.get(friend1), (Integer)list.get(friend2));
	    		
	    		sb.append(relation[find((Integer)list.get(friend1))] + "\n");
	    	}
	    }
	    

	    System.out.println(sb);
	}
	
	//x의 부모를 찾는 연산
	public static int find(int x) {
		if(x == parent[x])
			return x;
		
		return parent[x] = find(parent[x]);
	}
	
	// y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) {
			if(x < y) {
				parent[y] = x;
				relation[x] += relation[y];				
			}
			else {
				parent[x] = y;
				relation[y] += relation[x];				
			}
		}
		else {
			return;
		}
	}
	
}