여행 계획 짜기

문제

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

해설

소스코드

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

public class B1976 {
	static int n;
	static int m;
	static int[][] arr;
	static int[] city;
	static int[] route;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		arr = new int[n+1][n+1];
		city = new int[n+1];
		route = new int[m+1];
		
		for (int i = 1; i < n+1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < n+1; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i < m+1; i++) {
			route[i]=Integer.parseInt(st.nextToken());
			
		}	
		for (int i = 1; i < n+1; i++) {
			city[i]=i;
			
		}
		
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				if(arr[i][j]==1) {
					union(i,j);
				}
				
			}
		}
		
		int index = find(route[1]);
		for (int i = 2; i < route.length; i++) {
			if(index!=find(route[i])) {
				System.out.println("NO");
				return;	
			}
	
		}  
		System.out.println("YES");

	}

	private static int find(int a) {
		if(a == city[a]) {
			return a;
		}
		else {
			int result =find(city[a]);
			city[a]= result;
			return result;
			
		}
	}

	private static void union(int a, int b) {
		a = find(a);
		b= find(b);
		if(a<b) {
			city[b]=a;
			
		}else {
			city[a]=b;
		}
	}
}