[백준 P7511] 소셜 네트워킹 어플리케이션 Java

P7511 소셜 네트워킹 어플리케이션

7511번: 소셜 네트워킹 어플리케이션

문제

어렸을때부터 컴퓨터 프로그래밍에 엄청난 소질을 보인 상근이는 항상 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 상근이는 페이스북을 벤치마킹하기 위해 지난 3년간 열심히 사용을 했고, 이제 페이스북의 단점을 보완한 새 소셜 네트워킹 웹 2.0 어플리케이션을 만들려고 한다.

사람들은 소셜 네트워킹 어플리케이션에 가입을 한 다음, 현실에서 아는 사람을 친구로 추가하기 시작한다. 이러한 친구 관계 정보를 이용해 친구 관계 그래프를 그릴 수 있다.

소셜 네트워킹 어플리케이션에서 가장 중요한 기능은 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능이다. 경로가 없는 경우에는 보여주지 않는다.

상근이의 서비스는 매우 유명해졌고, 위의 기능은 사람들이 점점 많아질수록 경로를 구하는 시간이 매우 느려지게 되었다. 그 이유는 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문이었다. 따라서, 상근이는 두 사람 사이의 경로가 존재하는지 안 하는지를 미리 구해보려고 한다.

유저의 수와 각 유저의 친구 관계가 입력으로 주어진다. 이때, 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

입력값

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 유저의 수 1 ≤ n ≤ 1,000,000이 주어진다. 둘째 줄에는 친구 관계의 수 1 ≤ k ≤ 100,000가 주어진다. 다음 k개 줄에는 두 정수 0 ≤ a, b < n이 주어진다. 두 수는 친구 관계를 나타내며, 유저 a와 b가 친구라는 소리이다. 다음 줄에는 미리 구할 쌍의 수 1 ≤ m ≤ 100,000가 주어진다. 다음 m개 줄에는 구해야하는 쌍을 나타내는 u, v가 주어진다.

2
3
1
0 1
2
0 1
1 2
5
3
0 1
1 2
3 4
2
0 2
1 3

출력값

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

Scenario 1:
1
0

Scenario 2:
1
0

알고리즘

친구 관계에는 두 가지 경우의 수가 있다.

1. 만약 두 관계가 연결되지 않았다면, 두 사람 사이의 경로를 보여주지 않는다.
2. 만약 두 관계가 연결되어 있다면, 두 사람 사이의 경로를 보여 준다.

문제에서 구하고자 하는 것은 두 사람이 주어졌을 때 이 두사람이 서로 연결된 관계인가이다.

Union-Find 알고리즘을 사용하면 이를 쉽게 구할 수 있다. 두 사람의 관계를 입력받을 때 Union으로 두 관계를 연결하고 두 사람의 관계가 연결되어 있는지 확인할 때는 Find 값이 같은지 비교해서 결과를 출력하면 된다.

하나의 테스트 케이스를 살펴보겠다.

3
1
0 1
2
0 1
1 2

3명의 친구가 있고, 1개의 관계가 존재한다.

3명의 친구가 있으니 3개의 정수를 담을 수 있는 배열을 선언하고 각 요소는 스스로를 가리키게 한다.

그 다음, 1개의 관계를 입력받고 0, 1을 find해서 나온 결과값 중 더 큰 값에 작은 값을 할당한다. 이제 find(0)과 find(1)은 같은 값을 가지게 되고 이 둘이 연결되었다고 판단할 수 있다.

결과적으로 (0, 1)은 같은 값이 나오고 (1, 2)는 다른 값이 나오므로 (0, 1) = 1, (1, 2) = 0을 출력하면 된다.

코드

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

public class Main {
    static int TC, N, M;
    static int[] parent;

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

        TC = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= TC; tc++) {
            sb.append("Scenario " + tc + ":\\n");
            N = Integer.parseInt(br.readLine());
            parent = new int[N];

            for (int i = 1; i < N; i++) parent[i] = i;

            M = Integer.parseInt(br.readLine());

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                union(from, to);
            }

            M = Integer.parseInt(br.readLine());

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                if (find(from) == find(to)) sb.append("1\\n");
                else sb.append("0\\n");
            }

            sb.append("\\n");
        }

        System.out.print(sb);
    }

    public static void union(int a, int b){
        int aParent = find(a);
        int bParent = find(b);

        if (aParent < bParent) {
            parent[bParent] = aParent;
        } else if (bParent < aParent) {
            parent[aParent] = bParent;
        }
    }

    public static int find(int t) {
        if (t == parent[t]) return t;
        else return parent[t] = find(parent[t]);
    }
}