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

HashMap + unionFind

📑 문제

 

백준 4195 친구 네트워크

---

🌱 아이디어

위 문제에서 친구가 된 순서의 정보를 차례차례 제공한다.

그렇다면 단계마다 해당 친구가 속한 네트워크(집합)의 크기를 구하는 문제이다!

 

크게 생각해야 하는 점은 두 가지가 있다.

1. 친구의 정보가 이름(문자열)으로 제공되는 점
2. 친구 네트워크(집합)에 속한 크기를 구하는 방법.

 

1번의 경우는

HashMap을 사용하여 key : 이름 -> value : 번호로 치환해서 유니온파인드 알고리즘을 실행하면 된다.

당연히 해쉬맵에 이름이 있는지 판단해야 하고. 없다면 번호를 부여한다.

 

2번의 경우는

유니온 파인드 알고리즘을 사용하고 그중 union 함수에서

 

두 노드의 부모노드가 다르다면? -> 서로 다른 노드임 -> 친구가 되었기 때문에 ans [부모노드] += ans [자식노드]로 업데이트 후 출력

자식노드에 부모노드를 표시를 해준다, 즉 같은 친구네트워크 표시를 해준다.

 

두 노드의 부모노드가 같다면? -> 이미 같은 네트워크(집합) 임 -> 전에 합쳤기 때문에 그냥 출력 

 

이런 흐름으로 출력을 한다면 답을 구할 수 있다.

 

그리고 배열의 최대 크기를 200,000인 이유는

F == 100,000 인경우 친구 1, 친구 2 가 매번 다르다면 총 200,000의 친구(노드)가 생기기 때문이다.

---

🌱 코드 및 풀이

	public class Main {
	public static int[] parent;
	public static int[] ans;
	public static HashMap<String, Integer> map = new HashMap<>();
	// 부모노드 찾기
	public static int find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
	}
	// 집합에 포함하기.
	public static void union(int x, int y) {
	int from = find(x);
	int to = find(y);
	if (from != to) {
	// 서로 다른 노드였다면 해당 노드 별 친구 ans(부모노드)에 합치기.
	ans[from] += ans[to];
	parent[to] = from; // 부모노드 표시.
	}
	// 이미 친구라면 ans 배열을 더해줄 필요 없다.
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	StringBuilder sb = new StringBuilder();
	int T = Integer.parseInt(br.readLine());
	while (T-- > 0) {
	map = new HashMap<>();
	int F = Integer.parseInt(br.readLine());
	int cnt = 0;
	// 한 쌍의 친구 F <= 100,000 인 경우 최대 200,000명의 친구가 필요함.
	parent = new int[200_001];
	ans = new int[200_001];
	for (int i = 0; i < 200_001; i++) {
	parent[i] = i; // 자식노드에 부모노드 입력
	ans[i] = 1; // 집합에 속한 친구 수 입력
	}
	for (int i = 0; i < F; i++) {
	st = new StringTokenizer(br.readLine());
	String name1 = st.nextToken();
	String name2 = st.nextToken();
	// 해쉬맵에 없는 친구라면 입력하고 value에 번호 부여.
	if (!map.containsKey(name1)) {
	map.put(name1, cnt++);
	}
	if (!map.containsKey(name2)) {
	map.put(name2, cnt++);
	}
	// 친구별 번호로 union 연산하기.
	union(map.get(name1), map.get(name2));
	sb.append(ans[find(map.get(name1))]).append("\n");
	}
	}
	System.out.print(sb);
	}
	}

view raw 친구네트워크.java hosted with ❤ by GitHub

 

---

🌱 느낀 점

 

유니온 파인드 응용문제였다. 오랜만에 분리집합 문제를 풀었는데, 사실 전에 풀다가 포기한 문제였다.

그동안 다른 유형의 문제를 풀다 보니 풀 수 있게 되었다. 꾸준히 풀어보자