문제 설명

문제 분석

슈도코드

구현

public class 여행계획짜기_1976 {
    static int[] parent;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 도시 개수
        int N = scan.nextInt();
        int[][] cities = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cities[i][j] = scan.nextInt();
            }
        }

        // 여행 경로
        int M = scan.nextInt();
        int[] routes = new int[M+1];
        for (int i = 1; i <= M; i++) {
            routes[i] = scan.nextInt();
        }

        // 대표 노드
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        // 인접 행렬에서 도시가 연결되었다면 union 실행
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(cities[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        
        // 여행 경로의 도시들이 1개의 대표 도시로 연결된지 확인
        int index = find(routes[1]);
        for (int i = 2; i < routes.length; i++) {
            if(index != find(routes[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

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

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