백준(1976번) - 여행 가자

문제 출처: https://www.acmicpc.net/problem/1976

문제

• 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
• 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

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

public class Main {

    private static int[] parents;

    private static void makeSet(int n) {
        parents = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            parents[i] = i;
        }
    }

    private static boolean unionSet(int a, int b) {
        int parentA = findSet(a);
        int parentB = findSet(b);

        if (parentA == parentB) return false;

        parents[parentB] = parentA;

        return true;
    }

    private static int findSet(int a) {
        if (parents[a] == a) return a;

        return parents[a] = findSet(parents[a]);
    }

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

        int N = Integer.parseInt(reader.readLine()); // 도시의 수
        int M = Integer.parseInt(reader.readLine()); // 여행 계획에 속한 도시들의 수

        makeSet(N);

        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < N; j++) {
                if (Integer.parseInt(tokenizer.nextToken()) == 1) unionSet(i + 1, j + 1);
            }
        }

        String[] temp = reader.readLine().split(" ");
        boolean flag = true;
        for (int i = 0; i < temp.length - 1; i++) {
            if (findSet(Integer.parseInt(temp[i])) != findSet(Integer.parseInt(temp[i + 1]))) {
                flag = false;
                break;
            }
        }

        System.out.println(flag ? "YES" : "NO");
    }

}

• Union-Find 알고리즘을 적용하여 바로 풀 수 있는 문제였다.
• 주어진 입력대로 Union 연산을 수행 후, 마지막 줄에 들어오는 도시의 번호들이 같은 집합에 속하는지 즉, 대표자가 같은지 확인한다.