BOJ - 4195 ) 친구 네트워크

---

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

---

두명의 이름이 들어왔을때 이전 친구 그룹에 속하는지와 속하지 않으면 새로운친구 그룹을 만들면서 진행하는 문제이다

 

F=10만이기때문에 적절한 최적화를해주면 통과할 수 있다..

 

1 ) 두사람이 모두 HashMap에 없는경우

 

2 ) 한쪽만 HashMap에 있는 경우

 

3 ) 둘다 있는경우 

 

세가지로 나누어서 생각해보자.. 

1 ) 경우는 친구 그룹의 크기가 2가 항상 보장된다.

2 ) 경우는 친구 그룹이 결정된 그룹의 크기 +1 이 보장된다.

 3 ) 두 그룹의 합이 다음 친구 그룹의 합이되는게 보장된다.

 

따라서 이름 : 숫자 / 숫자 : 이름의 동적리스트 의 관계로 2개의 Map으로 해결하면 된다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class 친구네트워크 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < t ; i++) {
			st = new StringTokenizer(br.readLine());
			int tc = Integer.parseInt(st.nextToken());
			HashMap<String, Integer> hs = new HashMap<>();
			
			HashMap<Integer, ArrayList<String>> nameMap = new HashMap<>();
			for(int j = 0 ; j < tc ; j++) {
				st = new StringTokenizer(br.readLine());
				String name1 = st.nextToken();
				String name2 = st.nextToken();
				if(!hs.containsKey(name1) && !hs.containsKey(name2)) {
					// 둘다 없는 경우  j+1로 add
					hs.put(name1, j+1);
					hs.put(name2, j+1);
					nameMap.put(j+1, new ArrayList<String>());
					nameMap.get(j+1).add(name1);
					nameMap.get(j+1).add(name2);
					sb.append("2\n");
				} else if (!hs.containsKey(name1) && hs.containsKey(name2)) {
					int idx = hs.get(name2);
					hs.put(name1, idx);
					nameMap.get(idx).add(name1);
					sb.append(nameMap.get(idx).size() +"\n");
				} else if (!hs.containsKey(name2) && hs.containsKey(name1)) {
					int idx = hs.get(name1);
					hs.put(name2, idx);
					nameMap.get(idx).add(name2);
					sb.append(nameMap.get(idx).size() +"\n");
				} else {
					// 둘다있는경우 큰 쪽으로 Union 해준다.
					
					int idx_1 = hs.get(name1);
					int idx_2 = hs.get(name2);
					if(idx_1==idx_2) {
						sb.append(nameMap.get(idx_1).size() +"\n");
					} else {
						if(nameMap.get(idx_1).size() > nameMap.get(idx_2).size()) {
							for(int k = 0 ; k < nameMap.get(idx_2).size() ; k++) {
								String now = nameMap.get(idx_2).get(k);
								hs.put(now, idx_1);
								nameMap.get(idx_1).add(now);
							}
							nameMap.remove(idx_2);
							sb.append(nameMap.get(idx_1).size() +"\n");
						} else {
							for(int k = 0 ; k < nameMap.get(idx_1).size() ; k++) {
								String now = nameMap.get(idx_1).get(k);
								hs.put(now, idx_2);
								nameMap.get(idx_2).add(now);
							}
	
							nameMap.remove(idx_1);
							sb.append(nameMap.get(idx_2).size() +"\n");
						}
					}
				}
			}
		}System.out.println(sb);
	}

}

---