[백준]2458:키 순서 - JAVA

[백준]2458: 키 순서[백준]2458: 키 순서

www.acmicpc.net/problem/2458

2458번: 키 순서

풀이

키를 비교한 결과의 일부를 입력받고, 이를 통해서 유추할 수 있는 비교 순서를 모두 유추한 다음 확실하게 자신의 키가 몇 번째 인지 알 수 있는 학생의 수를 출력하는 문제이다.

 

모든 학생들의 비교 순서를 비교하면서 유추할 수 있는 비교 순서가 발견되면 값을 변경해 주기 위해 플로이드-와샬 알고리즘을 사용하였다.

 

풀이 순서는 다음과 같당.

1. MAX값으로 초기화한 배열을 준비한다.
2. 입력받은 비교 순서를 배열에 저장해 준다.
3. 플로이드-와샬 알고리즘을 사용하여 비교 순서를 알 수 있다면 갱신해 준다.
4. 배열을 순회하며 MAX가 아닌 거리값이 N - 1개인지 확인한다. (자기 자신으로 가는 경우를 제외한다.)

 

사실 이 문제는 프로그래머스의 '순위'문제와 매우 유사하다. 덕분에 바로 플로이드-와샬 알고리즘을 사용하여 풀었다.

 

코드

import java.util.*;
 
public class Main {    
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        int max = n * (n * (n - 1) / 2); //최대값
        
        int[][] student = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                student[i][j] = max; 
            }
        }
        
        for(int i = 0; i < m; i++) {
            int n1 = scan.nextInt();
            int n2 = scan.nextInt();
            student[n1 - 1][n2 - 1] = 1;
        }
        
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(student[i][j] > student[i][k] + student[k][j]) {
                        student[i][j] = student[i][k] + student[k][j];
                    }
                }
            }
        }
        
        int result = 0;
        for(int i = 0; i < n; i++) {
            int count = 0;
            for(int j = 0; j < n; j++) {
                if(student[i][j] < max || student[j][i] < max) count++;
            }
            if(count == n - 1) result++;
        }
        
        System.out.println(result);
    }    
}