[BOJ] 백준 4195번 친구 네트워크 (Java)

#4195 친구 네트워크

난이도 : 골드 2

유형 : 자료구조 / union-find

4195번: 친구 네트워크

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

처음에 문제 내용이 뭔가 부족하여 이해하기 어려웠다. 해당 문제는 서로소 집합 자료구조 문제로 친구 관계 (A B)가 주어지면 A B에 속해있는 친구 네트워크의 수를 구하면 된다.

 

📚 조건

• 친구 관계의 수 F ( 1 <= F <= 100,000)
• 친구 관계는 두 사용자 아이디로 이루어져 있다.

 

구상

1. String으로 되어있는 친구 아이디를 Map 자료구조를 사용하여 Integer형으로 저장한다.
2. 각 관계를 서로소 자료 집합구조를 사용하여 각 집합에 속해있는 원소의 갯수를 count하여 출력한다.

 

시뮬레이션

예제를 가지고 시뮬레이션을 돌려보자.

 

Map<Key,Value> = <FRED, 1>, <Barney, 2>, <Betty, 3>, <Wilma, 4>로 저장한다.

그리고 해당 자료들은 값이 낮을수록 순위가 높다고 가정한다. (부모 기준)

1) Fred Barney (1 2)

{1,2}

→ 서로소 집합의 크기는 2이다.

 

2) Betty Wilma (3 4)

{3,4}

→ 서로소 집합의 크기는 2이다.

 

3) Barney Betty (3 4)

{1,2,3,4}

→ 서로소 집합의 크기는 4이다.

 

 

 

위의 시뮬레이션과 같이 부모의 기준(낮은 index가 부모)을 정한 다음 해당 서로소 집합의 크기를 합쳐주는 식으로 union로직을 짜면 된다.

static int union(int x, int y) {
	x = find(x);
	y = find(y);

	if(x != y) { 
		if(x>y) { // y가 부모
			parents[x] = y;
			rank[y]+= rank[x];
			return rank[y];
		}else{  //x가 부모
			parents[y] = x;
			rank[x]+=rank[y];
		}
	} 
	return rank[x];
}

 

 

풀이 코드 

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

public class Main {

	static int[] parents, rank;
	static int size = 100_001;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		
		Map<String, Integer> map = new HashMap<>();
		for(int test=0; test<t; test++) {
			int f = Integer.parseInt(br.readLine());
			
			parents = new int[2*size];
			rank = new int[2*size];
			for(int i=1; i<2*size; i++) {
				parents[i] = i;
				rank[i] = 1;
			}
			
			int idx=1;
			for(int i=0; i<f; i++) {
				String line = br.readLine();
				st = new StringTokenizer(line);
				for(int j=0; j<2; j++) {
					String name = st.nextToken();
					if(!map.containsKey(name)) {
						map.put(name, idx++);
					}
				}
				
				String[] network = line.split(" ");
				int to = map.get(network[0]);
				int from = map.get(network[1]);
				int num = union(to,from);
				sb.append(num+"\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static int find(int x) {
		if(parents[x] == x) return x;
		int rx = find(parents[x]);
		return rx;
	}
	
	static int union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) { 
			if(x>y) { // y가 부모
				parents[x] = y;
				rank[y]+= rank[x];
				return rank[y];
			}else{  //x가 부모
				parents[y] = x;
				rank[x]+=rank[y];
			}
		} 
		return rank[x];
	}
}