백준 7511 - 소셜 네트워킹 어플리케이션

문제

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

리뷰

유니온 파인드를 이용하여 풀이할 수 있는 문제였다.

두 사람의 경로를 찾는다는 조건은 유니온 파인드에서 집합을 트리로 표현하였을때
두 노드가 같은 트리내에 속하는지(루트가 같은지 확인하는) 연산으로 처리할 수 있기
때문에 친구 관계를 union 연산을 통해 같은 루트 아래 속하도록 만들어주고
구해야하는 쌍을 받아 루트가 같은지 확인하여 결과를 도출하였다.

로직의 시간복잡도는 유니온 파인드의 시간복잡도인 $O(a(N))$으로 수렴한다.
여기서 $a(N)$은 역 아커만 함수를 의미하는데 $N$이 아무리 크더라도 왠만해선 4로
수렴하여 거의 상수값으로 볼 수 있다. 따라서 문제에서 주어진 $N$이 최대치인 $10^6$일
경우에도 제한 조건 1초를 무난히 통과한다.

코드

rank 를 이용한 최적화 유니온 파인드
rank 배열을 별도로 설정하여 각 노드별 자식 노드의 수를 저장한 후
깊이가 작은 트리를 깊이가 깊은 트리밑에 연결하므로써 트리의 깊이를 최소화한다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;


public class Main {
    static int[] parent;
    static int[] rank;

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

        int T = parseInt(br.readLine());
        int u, v;
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= T; i++) {
            int n = parseInt(br.readLine());
            parent = new int[n];
            rank = new int[n];

            for (int j = 0; j < parent.length; j++)
                parent[j] = j;
            Arrays.fill(rank, 1);

            int k = parseInt(br.readLine());
            while (k-- > 0) {
                st = new StringTokenizer(br.readLine());
                u = parseInt(st.nextToken());
                v = parseInt(st.nextToken());

                union(u, v);
            }

            int m = parseInt(br.readLine());
            sb.append("Scenario " + i + ":\n");

            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                u = parseInt(st.nextToken());
                v = parseInt(st.nextToken());

                sb.append(isSameRoot(u, v) ? "1\n" : "0\n");
            }

            sb.append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int find(int u) {
        if (parent[u] == u)
            return u;

        return parent[u] = find(parent[u]);
    }

    static boolean isSameRoot(int u, int v) {
        int root1 = find(u);
        int root2 = find(v);

        return root1 == root2;
    }

    static void union(int u, int v) { // O(a(N)) -> 거의 상수
        int root1 = find(u);
        int root2 = find(v);

        if (root1 == root2) return;

        if (rank[root1] > rank[root2]) {
            parent[root2] = root1;
            rank[root1] += rank[root2];
        } else {
            parent[root1] = root2;
            rank[root2] += rank[root1];
        }
    }
}

더 개선된 유니온 파인드
위 로직에서는 rank 배열을 추가로 사용하기 때문에 메모리를 더 소비하는 단점이 존재한다.
이런 단점을 개선하기 위해 parent 배열의 값을 다음과 같이 정의하여 로직을 개선할 수 있다.

• parent 의 값이 음수일 때
  parent[i] 의 절댓값은 i밑의 자식 노드 수를 의미한다. 이를테면 -3이면 자신을
  포함한 노드의 수가 3이라는 의미이다.
• parent의 값이 양수일 때
  parent[i]의 값은 자신의 부모 노드를 의미한다. parent[3]이 5라면 3의 부모는
  5이다.
  위 전제를 바탕으로 아래와 같이 로직을 구성한다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;


public class Main {
    static int[] parent;

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

        int T = parseInt(br.readLine());
        int u, v;
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= T; i++) {
            int n = parseInt(br.readLine());
            parent = new int[n];

            Arrays.fill(parent, -1);


            int k = parseInt(br.readLine());
            while (k-- > 0) {
                st = new StringTokenizer(br.readLine());
                u = parseInt(st.nextToken());
                v = parseInt(st.nextToken());

                union(u, v);
            }

            int m = parseInt(br.readLine());
            sb.append("Scenario " + i + ":\n");

            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                u = parseInt(st.nextToken());
                v = parseInt(st.nextToken());

                sb.append(isSameRoot(u, v) ? "1\n" : "0\n");
            }

            sb.append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0)
            return u;

        return parent[u] = find(parent[u]);
    }

    static boolean isSameRoot(int u, int v) {
        int root1 = find(u);
        int root2 = find(v);

        return root1 == root2;
    }

    static void union(int u, int v) { // O(a(N)) -> 거의 상수
        int root1 = find(u);
        int root2 = find(v);

        if (root1 == root2) return;

        if (parent[root1] < parent[root2]) { //더 작을 때가 깊이가 더 깊은 트리이다.
            parent[root1] += parent[root2];
            parent[root2] = root1;
        } else {
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
    }
}

결과

개선된 로직을 사용하였을때 메모리와 시간 복잡도 면에서 좀 더 우위를 가지는 것을
확인할 수 있었다.

참고

아래 글을 참고하여 유니온 파인드 알고리즘을 공부하고 작성한 글입니다.

https://velog.io/@chosj1526/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C#%EC%A0%95%EB%A6%AC