[프로그래머스/Level 3] 순위 (C++)

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

코딩테스트 연습 - 순위

플로이드 와샬을 이용하는 문제였습니다.

해당 알고리즘을 이용하여 모든 정점에서 다른 정점으로 갈 수 있는 여부(경기 결과를 알 수 있는지)를 확인합니다. 예를들어 a->b이고 b->c이면 a->c 가 된다는 것을 의미합니다. 

 

n = 5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 가 입력값으로 주어졌을 때, 플로이드 워셜을 이용하면 다음과 같이 배열이 완성됩니다.

 

출/도	1	2	3	4	5
1	false	true	false	false	true
2	false	false	false	false	true
3	false	true	false	false	true
4	false	true	true	false	true
5	false	false	false	false	false

 

또한 예시를 살펴보면, 2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 그리고 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다. 이를 통해 순위를 결정짓는 조건이 경기 결과가 중복없이 n-1회 발생해야 한다는 것을 확인할 수 있습니다.

 

5번 선수의 순위 결정

2번 선수의 순위 결정

위의 표를 보면 각각 true 값이 n-1번, 4번 나오는 것을 확인할 수 있습니다. 따라서 플로이드 와샬 알고리즘을 통해 위의 표와 같이 배열을 구하고, || 연산을 이용해 true의 값이 몇번 나오는지 확인해 순위가 결정되는 선수의 수를 구할 수 있습니다.

 

#include <string>
#include <vector>
using namespace std;

bool graph[101][101];

int F(int n) {
    int answer = 0;
    
    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] && graph[k][j]) graph[i][j] = true;
            }
        }
    }
    
    for(int i = 1; i <= n; i++) {
        int cnt = 0;
        for(int j = 1; j <= n; j++) {
            if(graph[i][j] || graph[j][i]) cnt++;
        }
        if(cnt == n - 1) answer++;
    }
    
    return answer;
}

int solution(int n, vector<vector<int>> results) {
    for(auto r : results) {
        graph[r[0]][r[1]] = true;
    }
    
    return F(n);
}