Lv 3. 순위

 

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

프로그래머스

 

 

 

이 문제는 플로이드-워셜 알고리즘을 사용해 해결하였다.
승패 정보를 바탕으로 선수들의 순위를 계산할 수 있는지를 판단하고,
정확한 순위를 알 수 있는 선수의 수를 반환한다.

순위는 승패 관계를 통해 간접적으로 계산되며,
모든 선수 간의 관계를 완전 탐색하여 결정한다.
먼저 graph 배열을 초기화하여 선수 간의 승패 관계를 저장한다.
승리 관계는 1로, 패배 관계는 -1로 설정되며,
초기 입력값을 기반으로 승패 정보를 저장한다.
이후 플로이드-워셜 알고리즘을 사용해 모든 선수 쌍에 대해 중간 선수를 거쳐 간접적으로 유추할 수 있는 승패 관계를 업데이트한다.
예를 들어, A가 B를 이기고 B가 C를 이기면
A가 C를 이긴다는 관계를 graph에 반영한다.

플로이드-워셜 알고리즘이 끝난 후,

각 선수에 대해 모든 다른 선수와의 승패 관계를 확인한다.

만약 특정 선수가 다른 모든 선수들과의 승패 관계를 알 수 있다면, 이는 그 선수의 순위를 정확히 알 수 있음을 의미한다. 이러한 선수를 answer 변수에 카운트한다.

 

 

class Solution {
    public int solution(int n, int[][] results) {
        int[][] graph = new int[n+1][n+1];
        for(int[] edge: results){
            graph[edge[0]][edge[1]] = 1;
            graph[edge[1]][edge[0]] = -1;
        }
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
                for(int k = 1 ; k <= n ; k++){
                    if(graph[i][k] == 1 && graph[k][j] == 1) {
                    	graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    if(graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }
        int answer = 0;
		
		for(int i = 0 ; i <=n; i++) {
			int count = 0;
			for (int j = 0; j <= n; j++) {
				if(graph[i][j] != 0) count++;
			}
			if(count == n-1) answer++;
		}
        return answer;
    }
}