[프로그래머스] 순위

문제

일부만 확인 가능한 경기 결과를 보고 순위를 매길 수 있는 선수의 수를 반환하면 된다.

---

풀이방법

풀이 시간 : 20분

풀이 방법 : 플로이드-워셜

 

플로이드-워셜 알고리즘을 사용해 문제를 풀이하면 된다.

https://90000e.tistory.com/10

[알고리즘] 플로이드-워셜 알고리즘

 

플로이드-워셜 알고리즘을 이용해 이기는 사람과 지는 사람의 모든 경우를 확인한다.

만약 1이 3한테 지고 4가 1한테 진다면, 4도 3에게 지는게 된다.

이런식으로 모든 경우를 확인한 후 자신을 제외한 모든 선수에게 이기고 지는지를 판단할 수 있으면 된다.

 

그래서 이길때는 1로 질때는 -1로 배열을 초기화 해주고 1번 선수부터 1과 -1의 갯수를 확인해 자신을 제외한 모든 인원수의 갯수와 똑같이 이기고 진 수를 확인할 수 있을때 순위가 결정될 수 있다고 판단했다.

---

코드

import java.util.*;
import java.io.*;

class Solution {
    static int[][] map;
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        map = new int[n+1][n+1];
        
        for(int i = 1; i <= results.length; i++){
            int a = results[i-1][0];
            int b = results[i-1][1];
            
            map[a][b] = 1;
            map[b][a] = -1;
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    if(map[i][k] == 1 && map[k][j] == 1){
                        map[i][j] = 1;
                        map[j][i] = -1;
                    }
                    if(map[i][k] == -1 && map[k][j] == -1){
                        map[i][j] = -1;
                        map[j][i] = 1;
                    }
                }
            }
        }
        
        for(int i = 1; i <= n; i++){
            int cnt = 0;
            for(int j = 1; j <= n; j++){
                if(map[i][j] != 0){
                    cnt++;
                }
            }
            if(cnt == n - 1){
                answer++;
            }
        }
        
        return answer;
    }
}