여행가자

in Algorithm on BeakJoon


백준 1976: 여행가자

문제보기
Alt text

풀이

연결 여부의 map 배열을 갱신시켜주어 map 배열만 보고 갈 수 있는지 판단.

예를 들어, 1에서 3으로 가고자하며 1과 2 연결, 2와 3이 연결 되어 있다고 하자.
그럼 (1,2)는 1이고 (1,3)은 0일 것이다. 1에서 2를 거쳐 3을 갈 수 있으니 결국 1에서 3으로 가는 것은 가능한 것. 따라서 (1,3)에도 1로 갱신을 해주자! 이때, (3,1)도 함께 1로 갱신.

소스코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	//도시의 수
		int M = sc.nextInt();	//여행 계획의 도시의 수
		int[][] map = new int[N+1][N+1];	//도시들 간의 연결 여부
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		int[] trip = new int[M];	//여행 계획
		for(int i=0; i<M; i++)
			trip[i] = sc.nextInt();
		
        //map배열을 갱신(갈 수 있는 경로가 존재하면 1로 바꿈)
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(map[i][j]==1) {
					for(int k=1; k<=N; k++) {
						if(map[j][k]==1) {
							map[i][k]=1;
							map[k][i]=1;
						}
					}
				}
			}
		}
		
		for(int i=1; i<=N; i++)
			map[i][i] =1;	//자기 자신(도시)은 방문가능
		
        //여행 계획대로 갈 수 있는지 판별
		boolean flag = true;
		int before = trip[0];
		for(int i=1; i<M; i++) {
			int after = trip[i];
			if(map[before][after]==0) {
				flag = false;
			}
			before = after;
		}
		
		if(flag)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}