[programmers] 순위

문제 풀이 : 2021.05.17

풀이

승자와 패자가 [승자, 패자] 형태로 주어지는데, 단방향 그래프의 출발과 도착으로 생각하고 풀면 된다.
승자 -> 패자 간선을 따라서 도착할 수 있는 최단 거리를 floyd warshall 을 이용해서 구하고, 자기 자신을 제외하고 '승자 -> 패자 and 패자 -> 승자' 의 값이 초기값이면 순위를 알 수 없는 경우이므로 제외한다.

코드

import java.util.*;

class Solution {
    static int[][] arr;
    static int answer;
    public int solution(int n, int[][] results) {
        arr = new int[n][n];
        for(int[] a : arr)
            Arrays.fill(a,1000);
        answer = n;
        for(int i = 0;i<results.length;i++){
            arr[results[i][0]-1][results[i][1]-1] = 1;
        }
        
         for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(i==j)
                    arr[i][j] = 0;
            }
         } 
        
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(arr[i][j]>arr[i][k]+arr[k][j])
                        arr[i][j] = arr[i][k]+arr[k][j];
                }
            }
        } 
        
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(i != j){
                    if(arr[i][j] == 1000 && arr[j][i] == 1000){
                        answer--;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
}

문제 출처 링크