[프로그래머스 / 그래프] 순위 (java)

[문제접근]

승패가 매겨진 배열을 통해 유방향 간선 그래프를 만들 수 있다. -> 플로이드 와샬 알고리즘 사용 

(처음에는 이 알고리즘이 생각이 안나서 다익스트라..? 이렇게 생각했는데 다른 사람들 풀이 보니까 플로이드 와샬로 하였음.)

가중치는 1로 두고 플로이드 와샬로 풀어주면 된다. 

 

플로이드 와샬 진짜 오랜만이다.. 다시 예전에 공부했던 것들 복습해야겠다.

 

[코드]

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int INF = 987654321;
        int[][] scores = new int[n+1][n+1];
        
        for(int[] score : scores){
            Arrays.fill(score, INF);
        }
        for(int i = 0; i < scores.length; i++){
            for(int j = 0; j < scores.length; j++){
                if(i == j)
                    scores[i][j] = 0;
            }
        }
        //그래프 추가 win->lose 방향으로
        // 간선으로 연결되어 있는 경우, 가중치는 1이라고 생각한다. 
        for(int[] result : results){
            int win = result[0];
            int lose = result[1];
            scores[win][lose] = 1;
        }
        // 플로이드 와샬 알고리즘
        // 최단경로 저장
        for(int k = 1; k < n + 1; k++){
            for(int i = 1; i < n + 1; i++){
                for(int j = 1; j < n + 1; j++){
                    if(scores[i][j] > scores[i][k] + scores[k][j])
                        scores[i][j] = scores[i][k] + scores[k][j];
                }
            }
            
        }
        
        //선수들이 서로 게임을 한 적이 있는지 확인
        boolean[] flag = new boolean[n+1];
        Arrays.fill(flag, true);
        for(int i = 1; i < n+1; i++){ // 선수 i 기준
            for(int j = 1; j < n+1; j++){ // 나머지 j 선수들과 게임 체크
                if(i == j) continue;
                
                if(scores[i][j] == INF && scores[j][i] == INF){
                    // 경로가 존재하지 않음. (i와 j가 게임을 하지 않음)
                    flag[i] = false;
                }
            }
        }
        
        for(int i = 1; i < flag.length; i++){
            if(flag[i]) answer++;
        }
        
        return answer;
    }
}

 

[참고]

https://iamheesoo.github.io/blog/algo-prog49191

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