[백준 - 자바] 4195. 친구 네트워크

이번 주의 문제

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

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

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

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

생각해본 풀이

import java.util.*;
import java.io.*;

public class 친구네트워크_4195 {
	
	static int[] parent;
	static int[] size;
	static Map<String, Integer> map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for(int tc = 1; tc <= T; tc++) {
			int F = Integer.parseInt(br.readLine()); //친구의 수
			
			parent = new int[F*2]; //모든 친구랑 친구했을 때 최대값
			size = new int[F*2];
			map = new HashMap<>();
			
			//친구관계
			for(int i = 0; i < 2*F; i++) {
				parent[i] = i;
				size[i] = 1;
			}
			
			int id = 0;
					
			for(int f = 0; f < F; f++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				String start = st.nextToken();
				String end = st.nextToken();
				
				if(!map.containsKey(start)) {
					map.put(start, id++);
				}
				
				if(!map.containsKey(end)) {
					map.put(end, id++);
				}
				
				//유니온 파인트 시작
				int group1 = find(map.get(start));
				int group2 = find(map.get(end));
				
				if(group1 != group2) {
					parent[group2] = group1; //총합하기
					size[group1] += size[group2];
				}
				
				sb.append(size[find(group1)]).append("\n");			
			}
		}
		
		System.out.println(sb);
	}
	
	public static int find(int x) {
		if(parent[x] != x) {
			parent[x] = find(parent[x]);
		}
		
		return parent[x];
	}
}

함께 보면 좋은 알고리즘

유니온 파인드(Union-Find)

집합 문제를 풀 때, 적용할 수 있는 알고리즘으로, 한 집합의 대표(parents)를 지속적으로 갱신하면서 같은 집합인지 아닌지를 판별한다. 여기서 그래프에서 연결되어 있으면 하나의 집합으로 본다.

이 알고리즘은 자기 자신 집합의 대표(parents)를 본인으로 초기화한 후에 시작한다. 이후 다른 그래프와 연결되면서 해당 노드의 대표를 갱신해주는데, 이를 union이라고 부르고, 다음과 같이 구현한다.

public static boolean union(int x, int y) {
	x = find(x); //x의 부모노드 찾기
	y = find(y); //y의 부모노드 찾기

	if(x == y) return false;
	
	if(x <= y) parent[y] = x;
	else parent[x] = y;
    
	return true;
}

둘의 부모가 같다면 같은 집합, 다르다면 다른 집합으로 보고, union, 즉 연결되어 지기 때문에 하나의 집합으로 합쳐지면서 대표를 둘 중 하나의 기준을 삼아 바꾼다. 위의 형식에서는 더 작은 쪽을 대표로 둔다.

public static int find(int x) {
	if(parent[x] == x) return x;
	return find(parent[x]);
}

부모를 찾는 메서드는 위와 같이 구현된다. 자기 자신이 대표인 노드를 만날 때까지 (시작점이 되는 노드까지) 올라가면 부모를 구할 수 있다.

현재 백준 문제에서는 union 알고리즘을 따로 빼지 않고 main 안에서 실행하고 있으며 find만 따로 빼서 사용하고 있다.

int group1 = find(map.get(start));
int group2 = find(map.get(end));
				
if(group1 != group2) {
	parent[group2] = group1; //총합하기
	size[group1] += size[group2];
}

부모를 찾아서 둘 중 하나로 합쳐주며, 해당 집합의 size 배열을 통해 친구 네트워크의 크기를 갱신해주고 있다.