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

 

 

이 문제는 n명의 권투 선수들이 참여한 권투 대회에서 각 선수의 순위를 매기려고 할떄, 주어진 경기 결과를 바탕으로 정확한 순위를 매길 수 있는 선수의 수를 찾는 것 입니다. 주어진 경기 결과를 2차원 배열 'results'로 표현되며, '[A , B]'는 A선수가 B선수를 이겼다는 의미입니다. 문제의 핵심은 경기 결과 일부가 분실되었음에도 불구하고, 가능한 순위를 정확하게 판단하는 것입니다.

 

문제 해결 방법

이 문제를 해결하기 위해 플로이드-워셜 알고리즘을 사용 합니다. 플로이드-워셜 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘 입니다. 여기서는 최단 경로 대신, 선수 간의 승패 관계를 파악하는 데 이 알고리즘을 응용합니다.

 

[JAVA/알고리즘] 플로이드-워셜 알고리즘 : 모든 쌍 최단 경로 탐색

 

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
         boolean[][] report = new boolean[n+1][n+1];
        int[] winCount = new int[n+1];
        int[] loseCount = new int[n+1];

        for(int i=0; i<results.length; i++){
            report[results[i][0]][results[i][1]] = true; //승리
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (report[i][k] && report[k][j]) {
                        report[i][j] = true;
                    }
                }
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i != j){
                    if(report[i][j]){
                        winCount[i] += 1;
                        loseCount[j] += 1;
                    }
                }
            }
        }

        for(int i=1; i<=n; i++){
            if(winCount[i] + loseCount[i] == n - 1){
                answer++;
            }
        }

        
        return answer;
    }
}

 

1. 초기화 : 먼저 , 각 선수간의 승패 관계를 나타내는 2차원 배열 'report' 를 초기화합니다. 배열의 크기는 선수의 수'n'에 1을 더한 값으로 설정합니다 ('n+1'), 이는 배열의 인덱스를 선수 번호와 직접 대응시키기 위함입니다.
2. 승패 관계 설정 : 주어진 경기 결과 'results'를 바탕으로 'report' 배열에 승패 관계를 기록합니다. 'result[i][0]' 이 'results[i][1]' 을 이겼다면, 'report[results[i][0]][result[i][1]]'을 'true'로 설정합니다
3. 플로이드-워셜 알고리즘 적용: 모든 선수 쌍에 대하여, 간접적인 승패 관계를 파악하기 위해 플로이드-워셜 알고리즘을 적용합니다. 선수 'i'가 선수'k'를 이기고, 선수'k'가 선수'j'를 이겼다면, 선수 'i'는 간접적으로 선수'j'를 이긴 것으로 간주하여 'report[i][j]'를 'true' 로 설정합니다.
4. 정확한 순위 판단 : 각 선수에 대하여, 직접적이거나 간접적인 승리와 패배의 총합이 'n-1'이 되는 경우, 해당 선수의 순위를 정확하게 판단할 수 있습니다. 이는 선수가 나머지 모든 선수와 승패 관계가 명확하게 정의되었음을 의미합니다.

 

플로이드-워셜 알고리즘을 이용하여 승패 관계를 파악을 하여 문제를 풀어 나가는게 맞습니다