[pro] 프로그래머스 level3 49191 순위 (Java) - 플로이드 와샬

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

[풀이]

i가 j에게 이겼다면, rank[i][j] = 1, rank[j][i] = -1 을 채운다.

플로이드 와샬 3중 for 문을 돌며, i가 k에게 이겼고, k가 j에게 이겼다면 rank[i][j] = 1, rank[j][i] = -1을 채운다.

자기 자신을 제외한 나머지 선수들과의 배열이 채워져있어서 n-1이라면 순위를 알 수 있다.

 

[코드]

 

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        //정확하게 순위를 매길 수 있는 선수의 수를 return
        
        int[][] rank = new int[n+1][n+1];
        //플로이드 와샬
        for(int[] r:results){
            rank[r[0]][r[1]] = 1; //이김
            rank[r[1]][r[0]] = -1; //짐
        }       
        
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(rank[i][k]==1 && rank[k][j]==1){
                        rank[i][j] = 1;
                        rank[j][i] = -1;
                    }
                }
            }
        }
        
        for(int i=1; i<=n; i++){
            int cnt = 0;
            for(int j=1; j<=n; j++){
                if(rank[i][j]!=0){
                    cnt++;
                }
            }
            if(cnt==n-1){
                answer++;
            }
        }
        return answer;
    }
}