[알고리즘] 백준 4195 친구 네트워크 -유니온 파인드- 자바

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

 

 

백준 유니온 파인드 단계별 풀기의 마지막 문제 친구 네트워크 문제입니다.  ㅎㅎ

 

이전에 풀어온 유니온 파인드 문제와 다르게 노드가 숫자가 아닌 문자열이 주어졌습니다. 

이를 해결하기 위해 HashMap<String, Integer>을 사용하여 이름(문자열)을 노드번호(Int)로 변환함으로써 기존의 숫자 노드를 활용한 문제처럼 바꿔줍니다.

또한 친구의 수를 구해야하므로 추가적으로 count 배열도 사용해주도록 합니다.

이 부분 빼고는 기존의 유니온 파인드 문제와 똑같습니다. 

 

주석과 코드를 보면 이해가 될겁니당. 

 

[Java]

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

class Main {
    private static int T; //테스트케이스 수
    private static int F; //친구 관계의 수
    private static int[] parent; //유니온 집합셋
    private static int[] count; //친구 관계 수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            F = sc.nextInt();
            parent = new int[F * 2];
            count = new int[F * 2];
            for (int i = 0; i < F * 2; i++) {
                parent[i] = i;
            }
            Arrays.fill(count, 1); //최초 친구 수는 기본값으로 한명이다
            HashMap<String, Integer> map = new HashMap<>(); // 이름, 인덱스(노드번호)
            int index = 0;
            for (int f = 0; f < F; f++) {
                String friend1 = sc.next();
                String friend2 = sc.next();
                if (!map.containsKey(friend1)) { //해당 친구이름이 아직 없는 경우 인덱스 부여
                    map.put(friend1, index++);
                }
                if (!map.containsKey(friend2)) {
                    map.put(friend2, index++);
                }
                System.out.println(union(map.get(friend1), map.get(friend2)));
            }
        }
    }

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

    private static int union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (a < b) {
                parent[b] = a; //집합 union
                count[a] += count[b]; //친구수 union
                return count[a];
            } else {
                parent[a] = b;
                count[b] += count[a];
                return count[b];
            }
        }
        return count[a];
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!