Menu

Subscribe

[JAVA/백준] 4195번: 친구 네트워크

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. 해시맵을 이용하여 각 이름에 인덱스를 부여한다.
  2. Union-Find 알고리즘을 이용해 각 이름별 부모를 저장한다.
  3. 부모간의 거리를 cnt[]에 저장한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	static int[] parent;
	static int[] cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		 int t=Integer.parseInt(br.readLine());
		 for(int i=0;i<t;i++) {
			 int f=Integer.parseInt(br.readLine());
			 HashMap<String, Integer> map=new HashMap<>();
			 parent=new int[f*2]; // 부모 연결 배열
			 cnt=new int[f*2]; // 부모간의 거리 저장 배열
			 Arrays.fill(cnt, 1); 
			 
			 int idx=0;
			 for(int j=0;j<f;j++) {
				 String[] str=br.readLine().split(" ");
				 // 처음 들어온 이름이면 해시맵에 put
				 if(!map.containsKey(str[0])) {
					 parent[idx]=idx;
					 map.put(str[0], idx++);
				 }
				 if(!map.containsKey(str[1])) {
					 parent[idx]=idx;
					 map.put(str[1], idx++);
				 }
				 
				 // union으로 연결
				 union(map.get(str[0]), map.get(str[1]));
				 // find하며 저장된 cnt값을 출력
				 System.out.println(cnt[find(map.get(str[1]))]);
			 }
		 }
		 
	}
	

	 public static void union(int a, int b) {
		 // 최상위 부모 찾기
		 int parentA=find(a);
		 int parentB=find(b);
		 // 같다면 이미 연결되어 있는 노드
		 if(parentA==parentB) return; 
		 
		 parent[parentB]=parentA; // a밑에 b가 들어감
		 cnt[parentA]+=cnt[parentB]; // b가 추가됐으므로 cnt[a] 갱신
	 }
	 
	 public static int find(int a) {
		 if(parent[a]==a) return a; // 더 이상 부모가 없음
		 return parent[a]=find(parent[a]); // 부모로 이동
	 }
	 
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 해시맵을 이용하여 이름에 인덱스를 부여한다
    • parent[]에는 부모의 인덱스를 저장하는 것이 편하므로 이름별 인덱스를 부여해야 한다.
    • 해시맵을 이용하여 들어오는 순서에 따라 인덱스를 부여한다.
    • key: 이름, value: 인덱스
    • 당연히 이전에 등록한 이름이 input으로 들어오면 패스한다.
    • 새 이름이 들어왔으므로 parent[idx]=idx로 초기화한다(내 부모는 나 자신).
  2. Union-Find 알고리즘을 이용한다
    • union: 파라미터 a, b를 연결하는 작업이다.
    • 둘의 최상위 부모를 찾아 parentA, parentB에 저장한다.
    • 두 값이 같다면 a, b는 이미 연결되어 있으므로 종료한다.
    • 아니라면, a 밑에 b가 들어가도록 한다.
    • 두 파라미터가 연결되었으므로 cnt[parentA]에 parentB의 개수들을 저장한다.
    • find: 파라미터 a의 최상위 부모를 찾는 메소드이다.
    • parent[a]=a라면 더 이상 부모가 없으므로 종료한다.
    • 아닐 경우 parent[a]의 부모를 찾는다.

👏 해결 완료!