[프로그래머스] 순위

문제 링크

 

풀이

이 문제는 모든 정점에 대해 최단 경로를 찾는 플로이드-워셜 알고리즘을 이용해 풀 수 있습니다. 주어진 예제를 통해 이 알고리즘을 어떻게 적용하는지 알아보겠습니다. 주어진 예제는 {4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5} 입니다.

{A, B}에서 A는 B를 항상 이깁니다
- 2는 네 번의 경기를 하므로 순위가 확정적으로 정해집니다
- 5번이 2번에게 확실하게 지는 거라면, 5번은 2번을 이기는 모든 선수에게도 집니다

- {4,2} {2,5}에서 {4,5}가 도출됩니다
- 그러므로 {4, 5}, {3, 5}, {1, 5}, {2, 5}가 성립합니다

코드

#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<vector<int>> results) {
    int answer = 0;    
    vector<vector<bool>> win(n + 1, vector<bool>(n + 1, false));    
    for (auto i : results)
        win[i[0]][i[1]] = true;
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                if (win[j][i] && win[i][k])
                    win[j][k] = true;

        for (int i = 1; i <= n; ++i)
    {
        int count = 0;
        for (int j = 1; j <= n; ++j)
        {    
            if (win[i][j] || win[j][i])
                ++count;
        }
        if (n - 1 == count) ++answer;
    }
    return answer;
}