백준 4195번 (java) 유니온파인드, Hash

백준 4195번 친구 네트워크 (java)

---

관찰

1. 네트워크의 크기를 구하기 위해서는 유니온 파인드를 통해서 집합을 만들어 줘야할 것 같다.

2. 문자열이기 때문에 hash를 사용해서 멤버를 관리해주자

3. 네트워크에 몇명이 있는지 구해야 한다. union-find 에 size(r 배열)가 더해진 버전이 필요하다!

---

정답 코드

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

public class Main {
    static int T,n; // 100000
    static HashSet<String> map;
    static String[][] name;
    static int[] p,r;
    static HashMap<String, Integer> friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(st.nextToken());
        for(int i=0;i<T;i++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            map = new HashSet<>();
            name = new String[n][2];
            friends = new HashMap<>();

            for(int j=0;j<n;j++){
                st = new StringTokenizer(br.readLine());
                String s1 = st.nextToken();
                String s2 = st.nextToken();
                map.add(s1);
                map.add(s2);
                name[j][0] = s1;
                name[j][1] = s2;
            }

            p = new int[map.size()+1];
            r = new int[map.size()+1];
            int size = map.size();
            for(int j=1;j<=size;j++){
                p[j] = j;
                r[j] = 1;
            }

            int k = 1;
            Iterator<String> it = map.iterator();
            while(it.hasNext()){
                friends.put(it.next(), k++);
            }

            for(int j=0;j<n;j++){
                union(friends.get(name[j][0]), friends.get(name[j][1]));

//                int max = Integer.MIN_VALUE;
//                for(int ii=1;ii<=size;ii++){
//                    if(max < r[ii]){
//                        max = r[ii];
//                    }
//                }

                int root = find(friends.get(name[j][0]));
                sb.append(r[root]).append("\n");
            }
        }
        System.out.println(sb);
    }

    private static void union(int a, int b) {
        int A = find(a);
        int B = find(b);
        if(A == B) return;
        if(r[A] < r[B]){
            r[B] += r[A];
            p[A] = B;
        }
        else{
            r[A] += r[B];
            p[B] = A;
        }
    }

    private static int find(int a) {
        if(a == p[a]) return a;
        else return p[a] = find(p[a]);
    }
}

---

풀이

(이번 풀이는 효율적인 방법은 아닌 것 같습니다.)

1. HashSet에 이름을 넣어주고 Iterator로 하나씩 뽑아주면서 총 몇명이 있는지 세어주고 HashMap에 순번과 이름을 넣어준다.

2. HashSet의 Size만큼 유니온 파인드를 하기 위한 p배열(parent)과 r(size)배열을 만들어준다.

3. 저장되어있던 입력을 다시 반복해주면서 이름에 맞게 union 해준다.

4. union을 해주면서 그 이름의 네트워크 사이즈를 출력해준다.

---

시행착오

시간초과를 처음 만났었는데 처음 코드는 주석에서도 볼 수 있듯이 size를 선형적으로 탐색을 해주었는데

그 부분을 root를 뽑아서 size를 바로 파악하도록 바꿔서 해결하였다.

---

마무리

내가 잘못 파악했던 것이 지금까지 써왔던 r 배열이 rank가 아니라 size였다...

사실 union에는 rank(size)가 중요한 문제가 없었는데 항상 이렇게 외워서 그냥 썼는데도 풀려왔었는데 이번에 rank(size)를 사용하는 문제를 만나면서 내가 이상하게 사용하고 있는 것을 알게되었다..

잘못알고 있는 것이 없나 다시한번 돌아봐야 할 듯 하다..