[BOJ] 4195. 친구 네트워크 - JAVA

🔗 문제

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

4195번: 친구 네트워크

 

💻 풀이 및 코드

문제 유형 : 자료 구조, 해시를 사용한 집합과 맵, 분리 집합

 

풀이

기존의 Union-Find 문제는 parent 배열만 있으면 됐지만, 이 문제는 노드가 정수형이 아닌 문자열로 주어지기 떄문에 3개의 변수가 필요하다.

• 기존의 부모 노드를 저장하는 int [] parent 배열
• 이름에 해당하는 parent 인덱스를 저장하는 Hashmap 
• parent 에 속한 집합의 갯수를 저장할 int[] cnt 배열

기존의 Union-Find 의 union 할 때 합쳐질 노드의 갯수를 부모 노드의 갯수에 더해주면 된다. ( cnt [ u ] += cnt [ v ] )

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicIntegerArray;

public class Main_bj_4195_친구네트워크 {
	
	static int[] parent;
	static int[] cnt;
	static Map<String, Integer> mp;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_4195.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for(int tc=0; tc<T; tc++) {
			int F = Integer.parseInt(br.readLine());
			
			init(F);
			
			int idx = 0;
			for(int i=0; i<F; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				String a = st.nextToken();
				String b = st.nextToken();
				
				if(!mp.containsKey(a)) {
					mp.put(a, idx++);
				}
				
				if(!mp.containsKey(b)) {
					mp.put(b, idx++);
				}
				
				sb.append(union(mp.get(a), mp.get(b))).append("\n");
			}
			
		}
		
		System.out.println(sb.toString());
		br.close();
	}
	
	static void init(int F) {
		parent = new int[F*2];
		cnt = new int[F*2];
		mp = new HashMap<>();
		
		for(int i=0; i<F*2; i++) {
			parent[i] = i;
			cnt[i] = 1;
		}
	}
	
	static int findParent(int x) {
		if(parent[x] == x) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	static int union(int a, int b) {
		int pa = findParent(a);
		int pb = findParent(b);
		
		if(pa == pb) return cnt[pa];
		parent[pb] = pa;
		cnt[pa] += cnt[pb];
		return cnt[pa];
	}

}

---

Reference

https://steady-coding.tistory.com/111

[BOJ] 백준 4195번 : 친구 네트워크 (JAVA)