[프로그래머스][코딩테스트 고득점 Kit][java] 순위

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

프로그래머스

참고

https://born2bedeveloper.tistory.com/45

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

bfs로 풀다가 길을 잃고 결국 답을 보고 말았다는 것,,

플로이드-워셜 알고리즘을 사용하는 문제였다

시간복잡도가 O(N^3) 이라 시간 제한이 까다롭지 않을 때만 사용할 수 있을 것 같다.

 

전체 코드

import java.util.*;

class Solution {
    static int[] visited;
    static int[][] graph;
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n+1][n+1];
        
        for(int i = 0; i < results.length; i++) 
            graph[results[i][0]][results[i][1]] = 1; //이김
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) {
                    // ex) i=3 j=2 k=5
                    // 3이 2를 이기고, 2가 5를 이긴다면
                    // 3은 무조건 5를 이기므로 graph[3][5] = 1로 갱신
                    if (graph[j][i] == 1 && graph[i][k] == 1)
                        graph[j][k] = 1;
                }
            }
        }
        
        // 순위를 알 수 있는 선수 count
        for (int i = 1; i <= n; i++) {
            int game = 0;
            for (int j = 1; j <= n; j++) {
                // graph[i][j] : i가 이긴 경우
                // graph[j][i] : i가 진 경우
                if (graph[i][j] == 1 || graph[j][i] == 1){
                    game++;
                }
            }
            if (game == n-1) answer++;
        }
        return answer;
    }
}