[BOJ-1613] 역사 -Java

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

1613번: 역사

package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class boj_1613_역사 {
	static int n,k, map[][];
	static List<int[]> sList=new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		map=new int[n+1][n+1];
		
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			
			map[start][end]=1;
			map[end][start]=-1;
		}
		
		int s=Integer.parseInt(br.readLine());
		
		for(int i=0; i<s; i++) {
			st = new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			sList.add(new int[] {start,end});
		}
		
		solve(bw);
		bw.flush();
		
	}
	private static void solve(BufferedWriter bw) throws IOException {
		

		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(map[i][k]==1 && map[k][j]==1) map[i][j]=1;
					if(map[i][k]==-1 && map[k][j]==-1) map[i][j]=-1;
				}
			}
		}
		
		int size=sList.size();
		for(int i=0; i<size; i++) {
			int []condition = sList.get(i);
			int start=condition[0];
			int end=condition[1];
			
			int result=-map[start][end];
			bw.append(-map[start][end]+"\n");
		}
	}
}

소요시간 : 50분

 

우선 사용한 알고리즘은 플로이드 - 와샬입니다.

 

일단 n의 크기가 400이기 때문에 n^3을 해도 요정도 밖에 안나오기 때문에 시간초과는 안납니다.

 

 

우선 방향그래프이기 때문에

start - end 는 1을 넣어주고 

end - start 에는 -1을 넣어줍니다.

여기서 1은 start- > end로 갈 수 있다는 뜻이고,

-1은 end->start로 갈 수 있다는 뜻입니다.

 

이렇게 플로이드 와샬을 통해서 모든 map을 채워준다음

 

조건 s를 판단해서 뽑아주면 됩니다.

 

끝~