[Programmers#49191] 순위

❒ Description

---

레벨	3
제목	순위
링크	https://school.programmers.co.kr/learn/courses/30/lessons/49191
자료구조	그래프
시간복잡도	O(V³)

 

이번 문제는 처음에는 Map과 PriorityQueue로 접근해서 풀어보려고 했다.

하지만 이 문제는 Floyd-Warshall 알고리즘을 응용해서 풀이하는 문제였다.

 

 

 

 

 

❒ 문제 분석

---

이번 문제의 목적은 선수의 순위를 매기는 것인데, 어떤 선수의 경우에는 정확하게 순위를 매길 수 없다.

그리고 [A, B], [B, C] 이렇게 되어있을 때 A는 B를 이길 수 있고, B는 C를 이길 수 있다. 이것을 바탕으로

A가 C를 이길 수 있다는 해석을 할 수 있다.

 

예시로 주어진 input 값을 그래프화 했다. 4번이 5번을 이길 수 있는지 확인해보자. [4,2], [2,5] 4는 2를 이기고,

2는 5를 이긴다. 이 뜻은 4 또한 5를 이길 수 있는 것이다. 이걸 코드로 구현하면 된다!!

 

 

 

 

 

 

❒ Solution

---

 

1. 그래프 생성

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

 

 

2. 경기 결과 반영

for (int[] result : results) {
    int winner = result[0];
    int loser = result[1];
    graph[winner][loser] = 1;
    graph[loser][winner] = -1;
}

 

 

3. Floyd - Warshall 알고리즘 수행

생각 할 포인트 : [4, 2], [2, 5] > [4,5] 

 

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            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;
            }
        }
    }
}

 

 

4. 순서를 매길 수 있는 모든 선수 count

생각 할 포인트 : 출전 선수가 n 명인 경우 각 선수가 참가할 수 있는 최대 경기 수는 n-1

int result = 0;
for (int i = 1; i <= n; i++) {
    int count = 0;
    for (int k : graph.get(i)) {
        if (k == 0) {
           count ++;
        }	
    }
    if (count == n-1) {
        result ++;
    }
}

 

 

 

 

 

 

---