[백준 Gold 2] 4195 친구 네트워크 - Java

문제링크 : https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

접근 과정 : 

• 익숙한 유형이라고 생각했다.
• 노드의 부모를 알 수 있는 자료구조와, 해당 노드가 부모인 그룹의 수를 저장하는 자료구조를 이용해서 풀이했다.
• 보통 익숙한 문제에서는 노드를 숫자로 주기때문에, 2개의 배열을 이용해서 쉽게 풀 수 있다.
• 해당 문제는 String값으로 노드가 주어졌고, 총 몇명의 친구가 주어지는지 확실하지 않았다.
• 그래서 HashMap으로 노드의 아이디를 저장하고, List를 통해 부모 노드와 그룹의 인원을 파악하려고 했다..
• 또 다른 방법으로는 친구의 최대 인원을 알 수 있기 때문에, 배열을 최대한으로 생성해놓고 풀이했다.
• 즉 HashMap+List / HashMap+Array 두개의 방법으로 풀이했다.

 

소스 코드 및 결과 :

/* 
    친구 네트워크
    
    HashMap + List
*/

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

public class BOJ4195_copy {

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

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int F = Integer.parseInt(br.readLine());

            friendsId = new HashMap<>();
            id = 0;
            root = new ArrayList<>();
            group = new HashMap<>();

            while (F-- > 0) {

                st = new StringTokenizer(br.readLine());
                int a = getID(st.nextToken());
                int b = getID(st.nextToken());

                a = findRoot(a);
                b = findRoot(b);

                if (a != b) {
                    root.set(b, a);
                    group.put(a, group.getOrDefault(a, 1) + group.getOrDefault(b, 1));
                }

                sb.append(group.get(a)).append("\n");

            }
        }

        System.out.println(sb.toString());
    }

    static HashMap<String, Integer> friendsId;
    static List<Integer> root;
    static HashMap<Integer, Integer> group;
    static int id;

    static int getID(String a) {
        if (!friendsId.containsKey(a)) {
            friendsId.put(a, id);
            root.add(id);
            id++;
        }

        return friendsId.get(a);

    }

    static int findRoot(int a) {
        if (root.get(a) == a) {
            return a;
        }

        root.set(a, findRoot(root.get(a)));

        return root.get(a);
    }

}

 

 

package BOJ;

/* 
    친구 네트워크
*/

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

public class BOJ4195 {

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

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int F = Integer.parseInt(br.readLine());

            HashMap<String, Integer> friendsId = new HashMap<>();
            int id = 1;
            root = new int[F * 2 + 1];
            group = new int[F * 2 + 1];
            Arrays.fill(group, 1);

            while (F-- > 0) {

                st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();
                friendsId.putIfAbsent(a, id++);
                friendsId.putIfAbsent(b, id++);

                int aRoot = findRoot(friendsId.get(a));
                int bRoot = findRoot(friendsId.get(b));

                if (aRoot != bRoot) {
                    root[bRoot] = aRoot;
                    group[aRoot] += group[bRoot];

                }

                sb.append(group[aRoot]).append("\n");
            }
        }

        System.out.println(sb.toString());
    }

    static int[] root;
    static int[] group;

    static int findRoot(int a) {
        if (root[a] == 0) {
            return root[a] = a;
        }
        if (root[a] == a) {
            return a;
        }

        return root[a] = findRoot(root[a]);
    }

}

 

P.S 

속도는 배열을 사용한 풀이가 더 빨랐다.