1976 여행 가자 [JAVA]

문제 분석

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

N개의 도시와 각 도시와 연결된 도시들에 대한 정보가 주어진다.

M개의 도시 방문 경로가 가능한 경로인 지 확인하여 가능하다면 YES 아니면 NO를 반환하면 되는 문제다,

 

여기서 경로에 대해 최적인지 판단할 필요가 없다.

따라서, 두 도시 사이에 어떠한 길이의 경로로든 연결만 되어 있다면 갈 수 있게 된다.

 

그렇기에 union find로 각 도시의 부모를 하나 정하고 두 도시의 부모 idx가 동일하면 같은 집합임을 의미하고 이는 곧 서로의 도시로 갈 수 있다는 뜻이 된다.

 

주의할 점은, m개의 방문 도시를 0,1, .. 이렇게 주는게 아닌, 1,2,... 이렇게 주니 인덱스를 애초에 1부터하던가 아니면 M개의 도시의 인덱스를 1 빼고 계산해야 한다.

 

코드

import java.util.*;

public class Main {
    static int[] parent;

    private static void union(int a, int b){
        int parentA = find(a);
        int parentB = find(b);

        int small = Math.min(parentA,parentB);
        int big = Math.max(parentA,parentB);
//        System.out.println(big+" 's parent will be "+small);
        parent[big] = small;
    }

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //방문 여부에 대해서만 알려주면 됨
        //a-b가 주어지면 b를 a에 포함시켜주면 됨
        int n = sc.nextInt();
        int m = sc.nextInt();

        //first can be ignored
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            sc.nextInt();
            parent[i] = i;
        }

        for (int i = 1; i < n; i++) {

            for (int j = 0; j < n; j++) {
                int isConnected = sc.nextInt();
                if(i==j)
                    continue;
                if(isConnected == 1){
                    union(i,j);
                }
            }
        }
        int startIdx = sc.nextInt();
        int firstParent = find(--startIdx);
        String answer = "YES";

        Set<Integer> targets = new HashSet<>();
        for (int i = 1; i < m; i++) {
            int nowIdx = sc.nextInt();
            targets.add(--nowIdx);
        }

        for (Integer target : targets) {
            int nowParent = find(target);
            if(firstParent != nowParent){
                answer = "NO";
                break;
            }
        }


        System.out.println(answer);

    }






}