[백준] 4195 - 친구 네트워크 (자바 Java)

[Gold II] 친구 네트워크 - 4195

문제 링크

성능 요약

메모리: 105968 KB, 시간: 1048 ms

분류

자료 구조(data_structures), 분리 집합(disjoint_set), 해시를 사용한 집합과 맵(hash_set)

문제 설명

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

---

union-find 알고리즘을 활용하면 된다.

기존의 문제들과 다른 점은 이름들이 string으로 주어지기 때문에 map을 활용한 것

배열의 크기가 정해져있지 않다는 점 -> ArrayList 또는 충분히 큰 배열을 선언

연결되어 있는 개수를 구해야 한다는 점이다.

 

처음에는 개수를 구할 때 부모가 같은 정점들을 하나씩 더하는 방법으로 계산했는데, 시간 초과가 났다.

그래서 union을 구현할 때 parent index에 합쳐진 index에 연결되어 있던 수들을 더해주었다.

package BOJ.Gold.g4;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BOJ_4195_친구네트워크 {

	static int[] p;
	static int[] rank;
	static Map<String, Integer> names;
	static int[] ans;
	static int size;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		while (T-- > 0) {
			int F = sc.nextInt();
			size = 0;
			p = new int[200000]; // 부모를 담을 곳..
			rank = new int[200000];
			names = new HashMap<>();
			ans = new int[200000];
			for (int i = 0; i < F; i++) {
				String f1 = sc.next();
				String f2 = sc.next();
				// 이름 찾기
				if (!names.containsKey(f1)) {
					int id = size++;
					ans[id] = 1;
					p[id] = id;
					names.put(f1, id);
				}
				if (!names.containsKey(f2)) {
					int id = size++;
					ans[id] = 1;
					p[id] = id;
					names.put(f2, id);
				}
				//////////////// 연결하기
				union(names.get(f1), names.get(f2));
				int cnt = ans[findSet(names.get(f1))];
				sb.append(cnt).append("\n");
			}
		}
		System.out.print(sb);
	}

	static int findSet(int i) {
		if (p[i] != i)
			p[i] = findSet(p[i]);
		return p[i];

	}

	static void union(int i, int j) {
		int pi = findSet(i);
		int pj = findSet(j);

		if (pi != pj) { // cycle 방지
			if (rank[pi] > rank[pj]) {
				p[pj] = pi;
				ans[pi] += ans[pj];
			} else {
				p[pi] = pj;
				ans[pj] += ans[pi];
			}
			if (rank[pi] == rank[pj])
				rank[pj] += 1;
		}
	}

}