[백준] 2458 - 키 순서

[문제링크]

2458번: 키 순서

 

0. 작은사람 -> 큰 사람 정보를 단방향 그래프로 표현

 

1. 플로이드 와샬 실행, 모든 노드에 대해 최솟값을 구한다

 

2. n번째 학생의 키 순서를 알기 위해선, 다른 모든 학생 k에 대해

  - k가 n보다 크거나 : n->k로 가는 길이 존재

  - n이 k보다 크거나 : k->n으로 가는 길이 존재

  - 둘 중 하나를 만족해야한다

 

3. 인접행렬의 adj[k][n] 혹은 adj[n][k] 둘 중 하나의 길이 존재해야한다

  - 두 값이 다 초깃값을 유지하고있다면 알 수 없음, 세지 않는다

 

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

public class Main{
	final static int maxV = 100000;

	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]adj = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(adj[i], maxV);
		}
		//방향 그래프
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int s = pint(st.nextToken())-1;
			int b = pint(st.nextToken())-1;
			adj[s][b]=1;
		}
		//플로이드
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					adj[i][j]=Math.min(adj[i][j], adj[i][k]+adj[k][j]);
				}
			}
		}
		//조건을 만족하는 학생 카운트
		int cnt=0;

		for (int i = 0; i < n; i++) {
			adj[i][i]=0;
			boolean chk=true;
			for (int j = 0; j < n; j++) {
				if(Math.min(adj[i][j],adj[j][i])==maxV) {
					chk=false;
					break;
				}
			}
			if(chk)cnt++;
		}
		
		System.out.println(cnt);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면