[백준] 친구 네트워크 4195 - java

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

4195번: 친구 네트워크

public class 친구네트워크 {
	static Map<String, String> parents;
	static Map<String, Integer> friends;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			int F = Integer.parseInt(br.readLine());
			parents = new HashMap<>();
			friends = new HashMap<>();
			for(int i=0; i<F; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				union(a, b);
				System.out.println(friends.get(parents.get(a)));
			}
			
		}
	}
	private static void union(String a, String b) {
		String rootA = find(a);
		String rootB = find(b);
		if(!rootA.equals(rootB)) {
			parents.put(rootB, rootA);
			friends.put(rootA, friends.get(rootA)+friends.get(rootB));
		}
	}
	private static String find(String a) {
		if(!parents.containsKey(a)) { // 초기값이 없으면 부모는 자기 자신
			friends.put(a, 1);
			parents.put(a, a);
			return a;
		}
		
		if(parents.get(a).equals(a)) return a;
		parents.put(a, find(parents.get(a)));
		return parents.get(a);
	}
}

union-find 문제입니다.

문자열을 가지고 비교해야되서 HashMap을 사용했는데

Fred Barney

   1      2

Barney Betty

          3

Betty Wilma

          4

각 문자열에 인덱스를 부여해서 기존의 방식과 동일하게 푸는 것이 더 간결하게 풀 수 있어보입니다.