백준 4195 - 친구 네트워크 (자바 - 분리 집합(Disjoint Set))

 

코딩 테스트 문제풀이 에서 처음으로 만난 분리 집합 문제

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

4195번: 친구 네트워크

 

처음 이 문제를 풀땐 두 사람의 이름이 입력될 때마다, 두 사람의 친구 네트워크 크기 값을 합산한 결과를 출력하는 것이므로 BFS 나 DFS 같은 단순 그래프 탐색 알고리즘으로 해결할 수 있을 것이라고 생각했다.

그런데 아무리 그래프 탐색 알고리즘을 통해 친구 네트워크의 크기를 구하여 합산해 보아도 정상적인 결과값을 출력하지 못했고, 결국 패스트 캠퍼스 코딩테스트 문제 해설 강의를 참고 하게 되었다.

 

최소 신장 트리의 크루스칼 알고리즘에서 사용되던 분리 집합(Disjoint Set) 알고리즘이 여기서??

강의 내용을 확인해본 결과 개념공부만 하고 기반 코드만 한번 작성해본지라 아직 숙련도가 부족했던 분리 집합 알고리즘을 이용해서 푸는 문제였다.

각 사람의 입력을 하나의 개별 집합으로 취급하고, 한 줄에 두 사람의 이름이 입력되면, 해당 두 사람은 그 입력을 통해 친구 관계가 맺어지는 것이므로, 각자의 친구 네트워크 내부에서 find 메소드를 통해 루트 노드를 찾은 후, 루트 노드가 서로 다른 것이 판명되면 특정 한 쪽의 루트 노드를 다른 한 쪽의 루트 노드로 설정 해주는 것으로 두 개의 개별 트리를 결합시켜(union) 서로 다른 친구 네트워크를 하나의 트리로 만들어준다.(크루스칼 알고리즘에서 사용되는 union-find 알고리즘이 사용되었다.)

 

코드는 다음과 같다.

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class FriendNetwork {
	
	static HashMap<String, String> parent = null;
	static HashMap<String, Integer> number = null;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		List<Integer> resultList = new ArrayList<Integer>();
		
		int count = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		for(int i = 0; i < count; i++) {
			int caseCount = Integer.parseInt(br.readLine());

			parent = new HashMap<String, String>();
			number = new HashMap<String, Integer>();
			
			for(int x = 0; x < caseCount; x++) {
				
				st = new StringTokenizer(br.readLine(), " ");
				
				String name1 = st.nextToken();
				String name2 = st.nextToken();
				
				parent.putIfAbsent(name1, name1);
				number.putIfAbsent(name1, 1);
				
				parent.putIfAbsent(name2, name2);
				number.putIfAbsent(name2, 1);
				
				union(name1, name2);
				
				/*
				 * 합 집합 찾기(Union-Find) 알고리즘
				 * - 원소들의 연결 여부를 확인하는 알고리즘 이다.
				 * - 현재 본인이 어떤 집합에 포함되어 있는지를 확인하는 것이 기본적인 원리
				 */
				
				resultList.add(number.get(find(name1)));
			}
			
		}
		
		resultList.stream().forEach(x -> {
			try {
				bw.write(x + "\n");
			} catch (IOException e) {
				e.printStackTrace();
			}
		});
		
		bw.flush();
		bw.close();
	}

	private static void union(String name1, String name2) {
		name1 = find(name1);
		name2 = find(name2);
		
		if(!name1.equals(name2)) {
			parent.put(name2, name1);
			int n = number.get(name1);
			number.replace(name1, number.get(name2) + n);
		}
		
	}

	private static String find(String name1) {
		
		if(name1.equals(parent.get(name1)))
			return name1;
		else {
			String p = find(parent.get(name1));
			parent.replace(name1, p);
			return p;
		}
	}
}

 - parent 는 각 개별 집합의 부모 노드를 나타내는 해시맵이고, number 는 각 사람이 소속 되어있는 트리의 높이 값을 나타내는 해시맵이다.

- 매 입력 마다 친구 네트워크가 결합된 이후 만들어진 트리의 높이를 출력시켜 주는 방식으로 문제를 해결하였다.

- 매 입력이 있을 때마다 부모 노드는 자기 자신(개별 집합으로 취급) 으로 설정하고 트리의 높이 또한 본인 밖에 없으므로 1로 설정해둔다.

- union 메소드의 경우 우선 입력받은 두 사람의 루트 노드 값을 find 메소드를 통해 찾아온다.

- find 메소드를 통해 찾아온 두 개의 루트 노드 값이 서로 같을 경우, 둘은 같은 트리에 속해있다는 뜻이므로 따로 트리 를 결합시키지 않는다.

- 만약 다를 경우 한쪽의 부모 노드를 다른 한쪽으로 설정해준 다음, 부모 노드로 설정된 사람의 기존 트리 높이값을 가져온 후 해당 높이 값을 합쳐진 노드의 트리 값을 합산한 값으로 바꿔주는 것으로 두 사람의 친구 네트워크 크기 통합 결과를 저장한다.

- find 메소드의 경우 입력 받은 사람의 부모 노드가 자기자신일 경우, 입력 받은 값이 곧 루트 노드라는 뜻이므로 입력 받은 사람을 그대로 반환해준다.

- 그렇지 않을 경우 입력 된 사람이 소속되어 있는 트리의 루트 노드를 재귀 호출을 통해 찾아 온 다음(앞전의 루트 노드의 조건을 만족하는 입력 값을 찾아내는 방식) 찾아진 루트 노드를 처음 find 메소드를 호출했던 스택부터 그 이후에 호출한 스택까지 모두 다 입력 값에 대한 루트 노드로 만들어 줌으로서 루트 노드의 이하에 있던 자식 노드들의 높이 값을 통일 시켜버린후 해당 루트 노드를 반환해줌 으로서 기존에 찾고자 했던 입력 값의 루트 노드 값을 반환받게 된다.