Programmers - 순위 with JAVA (V)

 

 

 

문제

격투 대회에서 각 참가자의 번호가 1~N으로 주어지고 대결 결과가 주어진다.

이 때, 순위를 정확히 알 수 있는 사람의 수를 구하라.

 

 

로직

이 문제는 shortest way의 플로이드 워셜 알고리즘 중에 정확한 순위 문제와 유사하다.

순위 문제는 종종 나오는데, 정확한 순위를 알 수 있는지 여부 문제와 정확한 순위가 무엇인지 문제, 정확한 순위를 알 수 있는 경우의 수 문제가 주어진다.

 

• 정확한 순위를 알 수 있는지 true/false : 위상 정렬을 사용하여 판단. 싸이클이 발생하는 경우(큐에서 꺼내는 값의 개수가 0인 경우), 두개 값의 순위 구별이 안되는 경우 (큐에서 꺼내는 값의 수가 두개이상인 경우)
• 정확한 순위가 무엇인지 : 위상정렬 활용 (위의 경우를 벗어나면 정확한 순위를 알 수 있다.)
• 정확한 순위를 알 수 있는 경우의 수 : 플로이드 워셜 알고리즘을 활용한다.

 

1. 일반적으로 (작은 값, 지는 노드, 더 점수가 낮은 노드) -> (큰 값, 이기는 노드, 더 점수가 높은 노드)로 인접행렬을 1로 설정한다.

2. 나머지는 INF로 한다.

3. x에서 y로 가는 경로와 x에서 i를 거쳐 y로 가는 경로를 비교해 플로이드 워셜 알고리즘으로 최단 경로를 구한다.

(이 떄, 순서는 i -> x -> y 순으로 for문을 작성한다.)

 

아이디어 : 만약, 결과적으로 a에서 b가 INF가 아니거나 b에서 a가 INF가 아니라면 비교 가능한 경우이다.

(INF 일 때는 둘의 관계를 모르거나 a가 높은 경우를 의미하고, 아니라면 b가 a보다 크다는 의미인데, 둘 다 INF 이면 따라서 비교가 불가능하게 되는 것이다.)

 

4. 이 후, 예를 들어, 노드 5까지 있을 때,

1-1, 1-2, 1-3, 1-4, 1-5

2-1, 2-2, 2-3, 2-4, 2-5

와 같은 방식으로 비교해 비교가 가능한 경우의 수가 5라면 모든 다른 수와 비교가 가능하다는 의미이므로 순위를 알 수 있는 경우로 판단한다.

 

 

아이디어 : 해당 노드와 비교 가능한 노드의 수가 n개 일 경우 순위 구별이 가능하다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        int[][] map = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i == j){
                    continue;
                }
                map[i][j] = (int)1e9;
            }
        }
        for(int[] result : results){
            map[result[1]-1][result[0]-1] = 1;
        }
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    map[i][j] =  Math.min(map[i][k] + map[k][j], map[i][j]);
                }
            }
        }
        int answer = 0;
        for(int i=0; i<n; i++){
            int count = 0;
            for(int j=0; j<n; j++){
                if(map[i][j] != (int)1e9 | map[j][i] != (int)1e9){
                    count += 1;
                }
            }
            if(count == n){
                answer += 1;
            }
        }
        return answer;
    }
}