백준 4195 친구 네트워크

친구 네트워크링크;https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

다음문제는 이전에 올려놓은 크루스칼 알고리즘을 응용한 문제 인데요

사실 크루스칼보다는 유니온 파인드를 사용하는 문제 입니다.

다음 문제는 입력받은 두사람의 친구 네트워크에 몇명이 존재하는지 출력 하는 문제입니다.

만약 처음에

 

Fred Barney가 입력이 되면 다음 두사람의 친구네트워크는

 

다음과 같이 되어 총 2명이 친구네트워크에 있을 것입니다.

다음으로 Barney Betty가 입력이되면 Barney는 Fred의 친구이므로 위의 그림에 Betty가 추가되어

다음의 친구 네트워크를 갖게 될것 입니다.

이후 Betty wilma가 입력되면 위에와 동일한 로직으로 총 4명의 친구네트워크를 갖게 됩니다

다음 예제는 어떻게 될까요?

처음 Fred barney가 입력되므로

이렇게 될것입니다 하지만 다음에 Betty Wilma가 입력되는데요 따라서다음과 같은 구조를 갖게 됩니다

마지막으로 Barney Betty가 입력되면 처음 예제와 같이 

다음의 친구 네트워크를 갖게 됩니다.

 

다음 문제를 풀기위해 각 인물마다 고유의 번호를 갖게 합니다

다음으로 해당 번호와 연결된 인원수를 저장할 Arr배열을 만듭니다.

1	2	3	4
1	1	1	1

처음에는 자신 밖에 없으니 1로 초기화를 해줍니다

이후 입력을 Fred Barney라고 받게 되면

둘중 하나의 번호로 다른 사람을 업데이트 해줍니다

업데이트가 되었다면 Fred가 갖고있는 번호의 인원수에 Barney가 갖고있는 번호의 인원수를 더해줍니다

1	2	3	4
2	0	1	1

  

Betty와 Wilma가 입력이되면 위의 과정 을 똑같이 해줍니다.

1	2	3	4
2	0	2	0

이후에 Barney Betty가 입력이 되면 

Betty와 연결되어 있는 친구들도 Barney의 번호로 전부 업데이트 시켜줍니다.

따라서 Arr배열은 다음과 같아 집니다

1	2	3	4
4	0	0	0

이것을 코드로 짠다면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 친구네트워크 {
	static int TC, F, friendCount;
	static Map<String, Integer> friendMap = new HashMap<>();//고유의 번호를 담아둘 map
	static int memberCount[];// 각 사람마다의 친구수
	static int parent[];// 자신의 부모를 넣어줄 배열

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			friendMap.clear();
			friendCount = 0;

			F = Integer.parseInt(br.readLine());
			String f1, f2;

			memberCount = new int[F * 2];
			parent = new int[F * 2];

			for (int f = 0; f < F; f++) {
				st = new StringTokenizer(br.readLine());
				f1 = st.nextToken();
				f2 = st.nextToken();

				if (friendMap.get(f1) == null) {
					parent[friendCount] = friendCount;// 부모 초기화
					memberCount[friendCount] = 1;
					friendMap.put(f1, friendCount++);
				}
				if (friendMap.get(f2) == null) {
					parent[friendCount] = friendCount;
					memberCount[friendCount] = 1;
					friendMap.put(f2, friendCount++);
				}
				System.out.println(unionFind(friendMap.get(f1), friendMap.get(f2)));
			}
		}
	}

	public static int getParent(int num) {
		if (num == parent[num]) {
			return num;
		} else {
			parent[num] = getParent(parent[num]);
			return parent[num];
		}
	}

	public static int unionFind(int num1, int num2) {
		int p1 = getParent(num1);
		int p2 = getParent(num2);

		if (p1 == p2) {
			return memberCount[p2];
		} else {
			parent[p1] = p2;
			memberCount[p2] += memberCount[p1];
			return memberCount[p2];
		}
	}
}

 같아집니다. 

제가 위에서 설명할때 parent배열과 map을 묶어서 설명했는데요.

코드를 구현하실때는 고유의 번호를 갖고있을 map과 친구들중 우두머리가 될친구의 번호를 유지시킬 parent배열을 따로 만드셔야 합니다.

 

처음 블로깅을하다보니 설명이 조금 난잡하네요ㅈㅅㅈㅅ

다음번엔 더깔끔하게 설명 해보겠습니다!!