[BOJ] 2458 키 순서

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

2458번: 키 순서

2022-06-26

---

import java.util.Arrays;
import java.util.Scanner;
 
public class Main2458 {
    public static int N, M;
    public static int[][] dist;
    public static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
 
        dist = new int[N+1][N+1];
 
        for(int[] i : dist) Arrays.fill(i, INF);
 
        for(int i = 0; i < M; i++) {
            dist[sc.nextInt()][sc.nextInt()] = 1;
        }
 
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    if(i == j) continue;
                    if(dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
 
        int answer = 0;
        for(int i = 1; i <= N; i++) {
            int cnt = 0;
            for(int j = 1; j <= N; j++) {
                if(dist[i][j] != INF || dist[j][i] != INF) cnt++;
            }
            if(cnt == N-1) answer++;
        }
 
        System.out.println(answer);
    }
 

 

#문제풀이

 

플로이드와샬 문제이다. 

 

모든 학생 ~ 모든 학생을 다 체크한 후, 어느 한 학생에서 다른 학생들의 키를 비교가 가능한 경우와 다른 학생들에서 어느 한 학생으로 비교가 가능한 경우의 수를 합 했을 때 N-1(본인에서 본인으로 가는 경우 빼기) 인 경우, 키를 알 수 있다고 보면 된다.