[백준] 7511 번 : 소셜 네트워킹 어플리케이션 - JAVA 풀이

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

분리집합 ( Disjoint Set ) 문제이다.

 

필요한 요소

1. makeSet() : 초기에 본인의 대표는 본인으로 초기화 해놓는 과정
2. int[] rep : 본인들마다 연결된 친구숫자 중 대표친구숫자를 저장한다.
   • 이때 대표친구숫자는 연결된 가장 작은수로 한다 ( 큰수보다 메모리 차지를 덜한다 )
3. int find(int x) : 본인의 대표친구를 찾는 find 함수
4. void unioin(int x,int y) : 두 대표를 친구로 연결해주는 함수
   • 두 대표 중 작은 숫자를 큰 숫자 대표로 rep 배열에 저장한다.

풀이 과정

a,b 두 사람을 친구로 연결해준다. “너의 대표를 가져와!”

1. 각각 두사람의 대표 A B 를 찾는다 A = find(a) B = find(b)
2. 두 대표중에 더 작은 수가 두 대표의 대표가 되어 더 큰수의 대표를 작은수로 바꿔준다.

u,v 두 사람이 친구인지 확인한다.

1. 각각 두사람의 대표 U,V를 찾는다 U = find(u) V = find(v)
2. U와 V가 같다면 1 같지 않다면 0

 

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

public class Main { // 분리집합 (Disjoint Set)

    static int[] rep;
    static int n;

    static void makeSet() {
        for (int x = 0; x < n; x++) {
            rep[x] = x; // 자기자신을 대표로 하는 과정
        }
    } // makeSet

    static void union(int x, int y) { // x와 y를 친구 맺는다
        // 일관되게 작은 숫자를 새로운 대표로 하자!
        if (x < y)
            rep[y] = x;
        else
            rep[x] = y;
    } // union

    static int find(int x) {
        if (x != rep[x])
            rep[x] = find(rep[x]);// 내 대표의 대표를 불러온다. ( 경로 압축 (path compression) : 대표의 대표를 찾았을 때 미리 저장해놓는 방식. 시간초과을 막아준다 )
        return rep[x];

        // return (x!=rep[x])? (rep[x]=find(rep[x])) : rep[x] ; // 할당해서 저장까지 해주고 반환할 수도 있다.

    } // find

    public static void main(String[] args) throws IOException {

        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int tc = Integer.parseInt(br.readLine()); // 테스트케이스

        for (int i = 1; i <= tc; i++) {

            sb.append("Scenario ").append(i).append(":").append("\n"); // 출력 첫 줄

            n = Integer.parseInt(br.readLine()); // 유저 수 (1~100만)
            int k = Integer.parseInt(br.readLine()); // 친구관계 수 (1~10만)

            rep = new int[n];
            makeSet();


            for (int j = 0; j < k; j++) {

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

                int A = find(a); // a의 대표
                int B = find(b); // b의 대표

                if (A != B) {
                    union(A, B);
                }
            }

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

            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                sb.append(find(u) == find(v) ? 1 : 0).append("\n"); // 둘의 대표가 같으면 친구, 같지 않으면 친구 아님
            }

            sb.append("\n");
        }

        System.out.print(sb);
        br.close();
    } // main
} // class