관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/유니온파인드, 최소신장트리(크루스칼)

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

막무가내막내 2020. 12. 21. 19:14
728x90

www.acmicpc.net/problem/4195

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

 

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

 

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

이를 해결하기 위해 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];
    }
}

 

 

 

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

728x90
Comments