프로그래머스 - 순위

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 순위

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

풀이 : 플로이드 와샬 알고리즘을 통해 선수 간의 경기 여부를 체크 한다.

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        boolean[][] chk = new boolean[n + 1][n + 1];
        for(int i = 0; i < results.length; i++) {
            chk[results[i][0]][results[i][1]] = true;
        }

        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(i != j && chk[i][k] && chk[k][j]) { // 플로이드 와샬 알고리즘
                        chk[i][j] = true;
                    }
                }
            }
        }

        for(int i = 1; i < n + 1; i++) {
            boolean pass = true;
            for(int j = 1; j < n + 1; j++) {
                if(i != j && !(chk[i][j] || chk[j][i])) { // i 와 j 간의 경기가 없으면
                    pass = false;
                    break;
                }
            }
            if(pass) answer++;
        }
        return answer;
    }
}