백준 | 4195번. 친구 네트워크 - 유니온 파인드 문풀

⬛ 백준 4195번. 친구 네트워크 - 유니온 파인드 문풀

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

4195번: 친구 네트워크

문제

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

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

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

입력

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

출력

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

---

💚 문제 접근 방식

• 친구 네트워크 또한 친구 관계 간 소속 집단을 만들어주고 그 소속 인원을 출력하는 문제이기 때문에 유니온 파인드의 전형적 유형이라고 볼 수 있다.

[실패 지점] : 소속 인원을 어떻게 계산해서 합칠 수 있을까 고민 돼서 헤맸다.

• 보통 인덱스 값을 기준으로 parent[] 에 대표 노드를 갱신하는 방식의 유니온 파인드를 활용했는데, 이 문제의 경우 입력이 String 형태로 들어오기 때문에 각 사람에 대해 유니크한 idx값을 지칭해주는 것이 중요하다.
• <name, num> 을 갖는 클래스를 선언해서 List에 담고 contains로 확인하며 풀까도 고민했지만, 결과적으로는 Map<String,Integer>를 활용해서 담은 뒤 , isContainsKey()로 중복없이 유니크한 idx값을 주도록 했다.
• 또한 최종 몇명의 친구가 들어올지 사이즈를 몰라서 parent선언 시 크기 지칭을 정확하게 할 수 없었기 때문에 우선은 입력되는 관계의 수 F*2 정도의 크기로 선언했다. (그 이상의 사람 수는 못 들어올테니까)

1) parent[]는 자기 자신에 대한 i를 대표노드로 갖도록 초기화해준다.

2) 여기서는 각 소속 인원을 처리해주기 위해 별도의 friends[] 배열이 필요하다. 여기서는 각 idx에 해당하는 사람의 소속 인원 수가 담길 예정이므로, 태초에는 모두 1로 초기화해준다. (왜냐하면 자기 자신에 대한 관계 1 )

3) Map에 중복없이 사람을 넣고, 그에 대한 중복없는 idx를 갖도록 처리한다.

4) 입력으로 들어오는 각 관계에 대한 union() 처리를 하는데, 이때 parent[]에 대표노드로 소속 처리 해주면서, freinds[]에도 각 사람의 소속 인원을 누적합 해주고, return 한다.

---

💚 제출 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 4195번. 친구 네트워크 - 유니온 파인드 문풀 
 * @author MYLG
 *
 */
public class Main {
	static int[] parent;
	static int[] friends;//각 i 별 친구 관계 수 저장용 
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		return parent[a] = find(parent[a]);
	}
	
	//union
	static int union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
			friends[a] += friends[b];
			friends[b] = 1; //1로 안해도 되긴 함 !!!
		}
		return friends[a];
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int TC = kb.nextInt();
		
		for(int t =0; t<TC; t++) {
			Map<String, Integer> map = new HashMap<>();
			int idx = 0;
			int F = kb.nextInt();
			parent = new int[F*2]; //최대
			friends = new int[F*2];
			for(int i=1; i<F*2; i++) parent[i]= i;
			
			Arrays.fill(friends, 1);//자기 자신에 대한 관계 1명 초기화
			
			for(int i = 0; i<F; i++) {
				String a = kb.next();
				String b = kb.next();
				
				if(!map.containsKey(a)) map.put(a, idx++);
				if(!map.containsKey(b)) map.put(b, idx++);
				
				System.out.println(union(map.get(a), map.get(b)));
			}
		}
	}
}

 

💚 회고

- 예전에 풀어본 적 있는 문제였음에도 다시 풀면서 굉장히 헤맸다. 

백준 | 4195번. 친구 네트워크 - 유니온 & 파인드, HashMap

- 유니온 파인드를 활용했을 때, 각 사람에 대한 소속 인원 수를 체크하는 부분을 초반에는 재귀로 현재 idx 지칭하는 대표 노드를 재귀로 거슬러 올라가면서 소속된 값을 카운팅하면 안될까 생각했는데... 정확히 뭐 때문인지 일부 값이 제대로 출력되지 않았다. 알아봐야 할 것 같다 .. 

	//union
	static int union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
		return findSize(a);
	}
	//소속 인원 크기 
	static int findSize(int a) {
		if(parent[a]==a) return 1;
		
		return 1 + findSize(parent[a]);
	}