본문 바로가기
알고리즘/백준

백준 2458 키 순서 (자바)

by 김어찐 2021. 9. 29.
728x90
package ct02hw_대전_6반_김어진;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N,K;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int[][] graph = new int[N+1][N+1];
		int[][] reverseGraph = new int[N+1][N+1];
		int INF = 100000000;
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				if(i==j) {
					graph[i][j]=0;
					reverseGraph[i][j]=0;
				}
				else {
					graph[i][j]=INF;
					reverseGraph[i][j]=INF;
				}
			}
		}
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine()," ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a][b]=1;
			reverseGraph[b][a]=1;
		}
		for (int k =1; k < N+1; k++) {
			for (int i = 1; i < N+1; i++) {
				for (int j = 1; j < N+1; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
					reverseGraph[i][j]=Math.min(reverseGraph[i][j], reverseGraph[i][k]+reverseGraph[k][j]);
				}
			}
		}
		int answer = 0;
		
		for (int i = 1; i < N+1; i++) {
			boolean check=true;
			for (int j = 1; j < N+1; j++) {
				if(graph[i][j]==INF && reverseGraph[i][j]==INF) {
					check=false;
					break;
				}
			}
			if(check==true)answer++;
		}
		System.out.println(answer);
	}
}
728x90