백준 1976 <여행가자>

플로이드 와샬로 풀거나 각각의 시작점을 두고 모든 방향을 DFS 또는 BFS를 하면 해결되는 간단한 문제이다.

 

다만 n^3승이기 때문에  각 도시들마다 돌때 이 방법을 수행해주면 200^3*1000 이므로 시간 초과가 난다.

 

이 문제에서 주의할 점은 현재의 도시 다음 계획에 속한 도시가 자기 자신일 수도 있다는 것이다!

 

문제 풀이

1. 각각의 마을을 시작점으로 두고 dfs를 통해 방문할수 있는 곳을 새로운 이차원 배열에 표시를 한다.
2. m개의 마을을 돌면서 방문할 수 없다면 boolean 값을 false로 두고 결과를 출력한다.

 

이렇게 모든 지점에서 방문할수 있는 마을을 체크하게 되면 n^3 만큼의 시간이 걸린다.

이렇게 해서 resultmap에 표시를 한다.

 

m개의 마을을 순서대로 갈수 있는지 체크하는 것이다. 시작 마을을 0부터 했기 때문에 1을 빼준다.

 

단순하게 모든 마을을 방문할수 있는지 계산하고 난 뒤 그 값을 이용하면 쉽게 풀리는 문제이다.

 

전체 코드

 

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

public class Main {	
	
	static int resultmap[][],map[][];
	static int n,m,sp;
	static boolean visit[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		m=Integer.parseInt(br.readLine());
		resultmap=new int[n][n];
		map=new int[n][n];
		StringTokenizer St;
		for(int i=0;i<n;i++) {
			St=new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j]=Integer.parseInt(St.nextToken());
				if(i==j) {
					resultmap[i][j]=1;
				}
			}
		}
		for(int i=0;i<n;i++) {
			sp=i;
			visit=new boolean[n][n];
			start(i);
		}//시작점에서 갈수있는지 모두 체크
		boolean flag=true;
		St=new StringTokenizer(br.readLine());
		int start=Integer.parseInt(St.nextToken())-1;
		for(int i=1;i<m;i++) {
			int next=Integer.parseInt(St.nextToken())-1;
			if(resultmap[start][next]==0) {
				flag=false;
				break;
			}
			start=next;
		}
		if(flag) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}
	private static void start(int i) {
		// TODO Auto-generated method stub
		for(int j=0;j<n;j++) {
			if(visit[i][j]||map[i][j]==0) {
				continue;
			}
			visit[i][j]=true;
			resultmap[sp][j]=1;
			start(j);
		}
	}
}