[Do It! 코딩테스트 자바편(김종관)] 문제 051(백준 1976번)

특징

• 도시 여행 경로가 주어지는데, 여행 경로에 포함된 도시가 전부 연결되어 있다면, 중간에 다른 도시를 거쳐 원하는 목적지로 갈 수 있다. 따라서 여행 경로에 포함된 도시가 전부 연결되어 있는지만 판별하면 여행 경로가 가능한지를 판별 가능하다.
• 여행 경로에 포함된 도시가 전부 연결되어 있는지는 유니온-파인드를 이용하면 된다.

문제

여행 가자 (백준: 1976번)

풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[][] adjacencyMatrix;
    static int[] travelRoute;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        adjacencyMatrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adjacencyMatrix[i][j] = sc.nextInt();
            }
        }
        travelRoute = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            travelRoute[i] = sc.nextInt();
        }
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        sc.close();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (adjacencyMatrix[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        int check = find(travelRoute[1]);
        for (int i = 2; i <= m; i++) {
            if (check != find(travelRoute[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    private static void union(int a, int b) {
        int rootOfA = find(a);
        int rootOfB = find(b);
        if (rootOfA != rootOfB) {
            parent[rootOfA] = rootOfB;
        }
    }

    private static int find(int index) {
        if (index == parent[index]) {
            return index;
        } else {
            return parent[index] = find(parent[index]);
        }
    }
}