[Programmers] LV3 - 순위

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

코딩테스트 연습 - 순위

 

문제 파악

 

1.results 배열에 선수끼리의 시합 결과가 주어진다. ( "[4,2]라면 4번 선수가 2번 선수를 이김")

2. 해당 결과를 가지고 순위의 파악이 가능한 사람은 몇 명인가?

 

다른 분들을 보아하니 LIST로 푸신 분도 있고 한데 나는 BOJ의 저울 문제가 생각나서 플로이드-와샬 알고리즘으로 풀었다.

 

import java.util.*;
class Solution {
    static final int INF = Integer.MAX_VALUE / 2;
    public int solution(int n, int[][] results) {
        int answer = 0;

        int[][] floyd = new int[n+1][n+1];

        for(int r = 1; r<=n;r++)
        {
            for(int c = 1 ; c<=n; c++){
                floyd[r][c] = r==c ? 0 : INF;
            }
        }

        for(int idx = 0; idx<results.length;idx++)
        {
            int r = results[idx][0];
            int c = results[idx][1];

            floyd[r][c] = 1;
        }

        for(int r = 1; r<=n; r++) // 경유지
        { 
            for(int c = 1; c<=n; c++) //시작점
            {
                for(int h = 1; h<=n; h++) // 도착점
                {
                    if(floyd[c][r]  == 1 && floyd[r][h] == 1){
                        floyd[c][h] = 1;
                    }
                }
            }
        }

        for(int r = 1; r<=n; r++)
        {
            int result = 0;
            for(int c=1; c<=n;c++)
            {
                if(floyd[r][c] == 1 || floyd[c][r] == 1){
                    result++;
                }
            }
            if(result == n-1){
                answer++;
            }
        }
        return answer;
    }
}