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

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

코딩테스트 연습 - 순위

문제

1. A선수가 B선수보다 실력이 좋으면 A선수는 B선수를 항상 이긴다.

2. 주어진 경기 결과로 선수들의 순위를 매기고자 하는데, 정확하게 순위를 매길 수 있는 선수의 수를 구해라

3. 경기는 1대1

 

해결과정

1. 선수의 수가 5명이면 4번의 경기 결과가 있는 1명이 존재하면 순위가 결정된다고 생각했었다. -> 실패

2. 1번의 예외케이스가 존재 -> ex) 1 > 2, 2 > 3,  3 > 4,  4 > 5 인 경우에 4번의 경기결과가 있는 선수가 존재하지않지만, 순위가 결정됨.

3. 그래서 모든 경기 결과를 최신화 시켜야한다고 생각 -> 플로이드 워샬

 

참고

남자친구가 짠 코드인데 그래프이론을 사용하지 않고 짠 코드이다.

https://jak141.tistory.com/17

그래프 - 순위

소스코드

package programmers.level3.rank;
 
public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution sol = new Solution();
        int n = 5;
        int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
        int result = sol.solution(n, results);
        System.out.println(result);
    }
 
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        int[][] fw = new int[n+1][n+1];
        
        for(int i = 0; i<n+1; i++) {
            for(int j = 0; j<n+1; j++) {
                if(i != j) {
                    fw[i][j] = 101;
                }
            }
        }
        
        for(int i = 0; i<results.length; i++) {
            fw[results[i][0]][results[i][1]] = 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(fw[i][j] > fw[i][k] + fw[k][j]) {
                        fw[i][j] = fw[i][k] + fw[k][j];
                    }
                }
            }
        }
        
        for(int i = 1; i<n+1; i++) {
            boolean flag = true;
            for(int j = 1; j<n+1; j++) {
                
                if(fw[i][j] == 101 && fw[j][i] == 101) {
                    flag = false;
                    break;
                }
            }
            
            if(flag) answer++;
        }
        
        return answer;
    }
    
}