[자바] 백준 1976 - 여행 가자

최단 경로를 찾는 것도 아니고, 다른 도시를 거쳐서라도 들를 수만 있으면 된다. 

유니온 파인드로 각 도시들의 최상위 parent를 찾고, 경로상의 도시들이 같은 parent인지만 체크하면 된다. 

/* 2021.01.02(토) */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	
	static int[] parent;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim());
		int M = Integer.parseInt(br.readLine().trim());
		
		parent = new int[N+1];
		for(int i=1;i<=N;i++) parent[i] = i;

		//유니온 과정 
		String[] str;
		int start,end, value;
		for(int a=1;a<=N;a++) {
			str = br.readLine().trim().split(" ");
			start = a;
			for(int b=1;b<=N;b++) {
				value = Integer.parseInt(str[b-1]);
				
				if(value==0) continue;
				end = b;
				union(start,end);
			}
		}
		
		//경로 체크
		str = br.readLine().trim().split(" ");
		int prevParent = -1;
		int city;
		String result = "YES";
		for(int i=0;i<M;i++) {
			city = Integer.parseInt(str[i]);
			if(i==0) prevParent = parent[city];
			
			if(prevParent!=find(city)) {
				result = "NO";
				break;
			}
		}
		System.out.println(result);
	}

	private static void union(int start, int end) {
		start = find(start);
		end = find(end);
		
		if(start==end) return;
		if(start<end) {
			parent[end] = start;
		}else if(start>end){
			parent[start] = end;
		}
	}

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