[BOJ] 1976 여행 가자(Flowd-Warshall)

문제

www.acmicpc.net/problem/11403

11403번: 경로 찾기

풀이

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

public class Main {
	static int N, M;
	static int[][] city;
	static int[] parent;
	static int[] trip;
	
	public static void Floyd_Warshall() {
		for(int k=1;k<=N;k++) {
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(city[i][k] == 1 && city[k][j] == 1)
						city[i][j] = 1;
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		//선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());//도시 수
		M = Integer.parseInt(br.readLine());//여행 계획 도시 수
		city = new int[N+1][N+1];
		trip = new int[M+1];
		//가능 경로 및 여행 경로 입력
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				city[i][j] = Integer.parseInt(st.nextToken());
			}
			city[i][i] = 1;
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=M;i++)
			trip[i] = Integer.parseInt(st.nextToken());
		//플로이드 와샬 적용
		Floyd_Warshall();
		
		//계산
		int start = trip[1];
		boolean chk = true;
		for(int i=2;i<=M;i++) {
			if(city[start][trip[i]]!=1 && city[trip[i]][start]!=1) {
				chk = false;
				break;
			}
			start = trip[i];
		}
		if(chk)
			System.out.println("YES");
		else
			System.out.println("NO");

	}

}