[프로그래머스][JAVA] 순위

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

방향성이 있는 그래프의 최단거리 알고리즘이다

선수들을 노드라고 생각하고 노드에서 노드의 최단 경로가 존재한다면 순위를 특정지을 수 있다 판단할 수 있고

없다면 순위를 특정지을 수 없다 판단할 수 있다.

그래프 최단거리 알고리즘의 대표적인 알고리즘인 플로이드 와샬 알고리즘을 적용하여 풀었다.

 

이때 max값은 Integer.MAX_VALUE로 할 경우에 max값을 서로 더해 비교하는 부분때문에 오버플로우가 발생한다

따라서 max 값은 문제 제한사항에 겹치지 않을만한 적당히 큰 수로 정하자

class Solution {
    int max = 1000000;
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] nodes = new int[n+1][n+1];
        for(int i =1;i<n+1;i++){
            for(int j = 1 ; j<n+1;j++){
                if(i==j){
                    nodes[i][j] = 0;
                }
                else{
                    nodes[i][j] = max;
                }
            }
        }
        
        for(int i =0;i<results.length;i++){
            //      win             lose
            nodes[results[i][0]][results[i][1]] = 1;
        }
        
        for(int i = 1;i<n+1;i++){
            for(int j = 1;j<n+1;j++){
                for(int k = 1; k<n+1;k++){
                    if(nodes[j][k]>nodes[j][i]+nodes[i][k]){
                        nodes[j][k] = nodes[j][i] + nodes[i][k];
                    }
                }
            }
        }
        
        boolean[] check = new boolean[n+1];
        for(int i =1;i<n+1;i++){
            check[i] = true;
        }
        for(int i =1;i<n+1;i++){
            for(int j = 1;j<n+1;j++){
                if(i!=j){
                    if(nodes[i][j]==max&&nodes[j][i]==max){
                        check[i]=false;
                        break;
                    }
                }
            }
        }
        
        for(int i =1;i<n+1;i++){
            if(check[i]){answer++;}
        }
        
        return answer;
    }
}