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

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

4195번: 친구 네트워크

 

 

처음에 Union - Find 알고리즘을 생각도 못하고 

 

정공법으로 풀려고 했으나

 

제한 시간과 여러 변수들이 많아 

 

어떤 알고리즘으로 풀어야했는지 검색했었다...

 

 

그 다음

 

Union - Find 알고리즘을 사용해서 정답은 유추했으나 시간 제한이 걸려버렸다. (심지어 3초인데도..)

 

그래서 이것저것 바꾸다가 알게된 사실은

 

HashMap이 탐색 시 가장 빠르다는 것.

 

 

필자는 처음 문자열과 그 문자열의 index를 넣기 위해 ArrayList를 사용했으나 

 

어차피 삽입 / 탐색 밖에 안하는 이 문자열과 index를 굳이 ArrayList를 사용했기 때문에

 

시간 초과가 발생했었다.

 

HashMap으로 변경하니 문제 해결!

*** LinkedHashMap을 사용해도 되지만, 어차피 value에 index를 넣기 때문에 상관이없다고 생각했다.

 

 

 

그렇지만

 

필자가 푼 해결방법은 시간이 넘나 소모되는 풀이였고..

 

그래서 베스트 해답을 참고해서 다시 풀었다.

 

 

 

이 해답의 풀이 방법을 간략히 적어보겠다.

 

 

 

  -  초기 모든 노드 값을 -1로 설정

 

  -  부모 노드는 음수로서 자식노드들의 크기를 담고 있고, 자식 노드들은 부모 노드의 인덱스를 가지고 있음

 

  -  둘 다 부모 노드일 경우 값 비교를 통해 절댓값이 작은 부모 노드를 큰 부모 노드에 이어붙인다.

  *** 절댓값이 작다는 뜻은 결국 네트워크 자식들의 개수가 작다는 것

  -  굳이 자식 노드들 전부 변경하지 않고 부모 노드만 한 번 바꿔놓으면 어차피 find 함수를 통해 최상단 부모 노드를 찾을 수 있음
 

  -  그래서 네트워크의 크기 계산까지 가능하게 됨

 

 

 

 

 

자세한 부분은 소스코드를 참고하시면 좋겠습니다.

 

 

감사합니다!

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.HashMap;
	import java.util.StringTokenizer;
	// Disjoint-set
	// union-find
	public class p4195 {
	static int[] disjointSet;
	static HashMap<String, Integer> names;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int tc = Integer.parseInt(st.nextToken());
	StringBuilder sb = new StringBuilder();
	while(tc --> 0) {
	st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken());
	disjointSet = new int[(2 * n) + 1];
	Arrays.fill(disjointSet, -1);
	names = new HashMap<String, Integer>();
	int nowIndex = 1;
	for(int i = 0; i < n; i++) {
	st = new StringTokenizer(br.readLine());
	String a = st.nextToken();
	String b = st.nextToken();
	int size = 0;
	int aIndex, bIndex;
	if(names.containsKey(a)) {
	aIndex = names.get(a);
	}
	else {
	names.put(a, nowIndex);
	aIndex = nowIndex++;
	}
	if(names.containsKey(b)) {
	bIndex = names.get(b);
	}
	else {
	names.put(b, nowIndex);
	bIndex = nowIndex++;
	}
	size = -merge(aIndex, bIndex);
	sb.append(size).append("\n");
	}
	}
	System.out.println(sb.toString());
	}
	// 베스트 정답.
	// 초기 모든 노드 값을 -1로 설정
	// 부모 노드는 음수로서 자식노드들의 크기를 담고 있고, 자식 노드들은 부모 노드의 인덱스를 가지고 있음
	// 둘 다 부모 노드일 경우 값 비교를 통해 절댓값이 작은 부모 노드를 큰 부모 노드에 이어붙인다.
	// 굳이 자식 노드들 전부 변경하지 않고 부모 노드만 한 번 바꿔놓으면 어차피 find 함수를 통해 최상단 부모 노드를 찾을 수 있음
	// 그래서 크기 계산까지 가능하게 됨
	// 그저 갓.
	private static int merge(int aIndex, int bIndex) {
	aIndex = find(aIndex);
	bIndex = find(bIndex);
	if(aIndex != bIndex) {
	if(disjointSet[aIndex] > disjointSet[bIndex]) {
	disjointSet[bIndex] += disjointSet[aIndex];
	disjointSet[aIndex] = bIndex;
	}
	else {
	disjointSet[aIndex] += disjointSet[bIndex];
	disjointSet[bIndex] = aIndex;
	}
	}
	return disjointSet[aIndex] < 0 ? disjointSet[aIndex] : disjointSet[bIndex];
	}
	// 루트 노드를 찾는 함수
	static int find(int index) {
	if(disjointSet[index] < 0) { // 부모 노드의 값이 개수(음수)이기 때문에 이 코드는 사용할 수 없음
	return index;
	}
	return disjointSet[index] = find(disjointSet[index]);
	}
	}

view raw p4195.java hosted with ❤ by GitHub