[BOJ-4195][Union-Find] 친구 네트워크 -Java

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

4195번: 친구 네트워크

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class boj_4195_친구네트워크 {
	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));

		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			int F = Integer.parseInt(br.readLine());
			int parents[]=new int[(F*2)+1];
			int sum[]=new int[(F*2)+1];
			make_set(parents, sum);
			HashMap <String, Integer> arrayIdx = new HashMap<>();
			int idx=0;
			for (int i = 0; i < F; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String name1=st.nextToken();
				String name2=st.nextToken();
				//name1, name2 이름 없으면 넣어주고 인덱스 +1
				if(!arrayIdx.containsKey(name1)) {
					arrayIdx.put(name1, idx++);
				}
				
				if(!arrayIdx.containsKey(name2)) {
					arrayIdx.put(name2, idx++);
				}
				
				
				bw.write(union_set(arrayIdx.get(name1), arrayIdx.get(name2),parents, sum)+"\n");
			}

		}
		bw.flush();
	}
	public static int union_set(int x, int y,int []parents, int []sum) {
		x=find_set(x, parents);
		y=find_set(y, parents);
		
		if(x!=y) { 
			parents[x]=y; //부모 바꿔주고
			sum[y]+=sum[x];
		}
		return sum[y];
	}
	
	public static int find_set(int num, int []parents) {
		if(num==parents[num]) return num;
		return parents[num]=find_set(parents[num], parents);
	}
	public static void make_set(int []parents, int []sum) {
		for(int i=0; i<parents.length; i++) {
			parents[i]=i;
		}
		for(int i=0; i<sum.length; i++) {
			sum[i]=1;
		}
	}

}

소요시간 : 50분

 

아 네이버 대비한다고 IDE자동완성 안쓰고 하니까 좀 빡세네요....

우선 문제는 전형적인 Union-Find문제입니다. 좀 다른 점은 숫자가 아니고 문자라는점?

 

근데 이 문자를 HashMap을 통해서 숫자로 만들어서 사용했습니다.

F의 제한조건이  F<=100,000이기 때문에 모두 다른 친구가 들어왔다고 하면 parents의 크기는 F*2만큼 필요합니다.

그리고 친구 네트워크에 몇 명이 있는지 구하기 위해서 sum이라는 배열을 만들었습니다.

 

두 집합이 합쳐지는 과정에서 한쪽의 집합의 크기를 반대쪽 집합의 크기로 넣어주는 작업을 통해

한번에 친구네트워크의 크기를 구할 수 있습니다.

 

끝~!