백준 1976 - 여행 가자

문제

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

리뷰

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

0-1 행렬 형태로 들어오는 노드들의 관계를 유니온 파인드 연산을 이용하여 분리집합으로
표현한 뒤 방문하는 도시들의 루트를 find 연산을 통해 찾아 하나라도 루트가 같지 않은
것이 나올 경우 경로가 존재하지 않는 경우이므로 NO를 출력해주는 식으로 로직을 구성했다.

로직의 시간 복잡도는 유니온 파인드의 시간 복잡도인 $O(a(N))$으로 수렴하고 역 아커만 함수인
$a(N)$은 $N$이 아무리 크더라도 거의 4로 수렴하기 때문에 상수 시간으로 볼 수 있다.
따라서 $N$이 200인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

아래 최적화된 유니온 파인드 로직에 대한 자세한 설명은 아래 링크를 참고하면 된다.
https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-7511-%EC%86%8C%EC%85%9C-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%82%B9-%EC%96%B4%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98

코드

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

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));
        int N = parseInt(br.readLine());
        parent = new int[N + 1];
        Arrays.fill(parent, -1);

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

        StringTokenizer st;
        for (int u = 1; u <= N; u++) {
            st = new StringTokenizer(br.readLine());
            for (int v = 1; v <= N; v++) {
                int value = parseInt(st.nextToken());

                if (value == 1)
                    union(u, v);
            }
        }

        st = new StringTokenizer(br.readLine());
        int pre = find(parseInt(st.nextToken()));
        while (st.hasMoreTokens()) {
            int current = find(parseInt(st.nextToken()));
            if (pre != current) {
                System.out.print("NO");
                return;
            }
        }

        System.out.print("YES");
        br.close();
    }

    static int find(int u) { // O(a(N)) 
        if (parent[u] < 0) return u;

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

    static void union(int u, int v) { // O(a(N))
        int root1 = find(u);
        int root2 = find(v);

        if (root1 == root2) return;

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

결과