[백준] 4195 : 친구네트워크 [JAVA] 골드2

백준

 

문제 풀이 설명 (summary)

• 유니온 파인드 활용
  • 여러 개의 원소가 있을 때, 이 원소들이 같은 집합에 속해 있는지 여부를 빠르게 판단
  • 서로 다른 집합을 하나로 합치는 연산을 효율적으로 수행

 

문제 풀이 접근법

• 매번 테스트 케이스마다 네트워크 활성화 된 친구를 어떻게 계산할지 (key)
• 각 노드별로 크기를 key를 이용해 저장해놓고 union 합산할 때 key도 더해줌
• 숫자가 아닌 문자열을 어떻게 배열로 관리할 지 (key)
• hashMap을 통해 문자열마다 value (-parent key) 값을 할당해서 필요할 때 꺼내씀

 

풀이 코드 (Code)

public class Main {

    static int[] parents;
    static int[] sizes; // 각 집합의 크기
    static HashMap<String, Integer> nameMap;
    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 t = 0; t < T; t++) {
            int F = Integer.parseInt(br.readLine());
            parents = new int[F * 2 + 1];
            sizes = new int[F * 2 + 1];
            nameMap = new HashMap<>();

            // 초기화
            for (int i = 0; i <= F * 2; i++) {
                parents[i] = i; // 자기 자신이 부모
                sizes[i] = 1;   // 초기 크기는 1
            }

            for (int i = 0; i < F; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String name1 = st.nextToken();
                String name2 = st.nextToken();

                int num1 = getNumber(name1);
                int num2 = getNumber(name2);

                // Union 연산으로 연결
                sb.append(Union(num1, num2)).append("\n");
            }
        }
        System.out.print(sb); // 결과를 한 번에 출력
    }

    private static int getNumber(String name) {
        if (!nameMap.containsKey(name)) {
            nameMap.put(name, nameMap.size() + 1);
        }
        return nameMap.get(name);
    }



    private static int Union(int x, int y) {
        x = Find(x);
        y = Find(y);

        if (x != y) {
            if (sizes[x] < sizes[y]) {
                parents[x] = y;
                sizes[y] += sizes[x];
                return sizes[y];
            } else {
                parents[y] = x;
                sizes[x] += sizes[y];
                return sizes[x];
            }
        }
        return sizes[x]; // 이미 같은 집합이라면 크기 반환
    }

    private static int Find(int x) {
        if (x == parents[x]) return x;
        return parents[x] = Find(parents[x]);
    }
}

 

문제 링크 (Link)

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