프로그래머스 - 순위

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

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드 워셜 알고리즘을 응용하여 푼다.

플로이드 워셜 알고리즘은 (i, j) > (i, k) + (k, j) 인 경우에 최단거리를 갱신한다.

이 문제에서, A가 B에게서 이기고, B가 C에게서 이긴 경우, A가 C를 이길 수 있다고 추가한다.

그렇게 해서 사람 한명에 대해서 n - 1명의 승패를 계산할 수 있는지 확인한다.

import java.util.*;

class Solution {
    private final static int u = 0;
    private final static int v = 1;
    
    private boolean[][] graph;
    
    public int solution(int n, int[][] results) {
        initW(n, results);
        
        winnerCheck(n);
        
        return getAnswer(n);
    }
    
    private void initW(int n, int[][] results) {
        graph = new boolean[n + 1][n + 1];
        
        for (int[] edge : results) {
            graph[edge[u]][edge[v]] = true;
        }
    }
    
    private void winnerCheck(int n) {
        for (int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    if (graph[j][i] && graph[i][k]) {
                        graph[j][k] = true;
                    }
                }
            }
        }
    }
    
    private int getAnswer(int n) {
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] || graph[j][i]) {
                    count++;
                }
            }
            
            if (count == n - 1) {
                answer++;
            }
        }
        
        return answer;
    }
}