[프로그래머스 lv3] 순위 풀이

해설

n의 입력값이 100이하 이므로, 시간복잡도가 O(V^3)인 플로이드 와샬 알고리즘으로 해결할 수 있다.

 

i가 k를 이길 수 있고, k가 j를 이길 수 있을 때, i는 j를 이길 수 있다.

따라서, dp[i][k] == true 이고 dp[k][j] == true 이면 dp[i][j] = true 이다.

 

위의 사실을 이용하여 이길 수 있는 모든 경우를 구해놓은 뒤, 특정 선수에 대하여 이기는 경우의 수와 지는 경우의 수를 모두 세어보자.

특정 선수가 이기는 사람 수를 nwin, 특정 선수가 지는 사람 수를 nloss라고 했을 때 nwin+nloss-1(본인 제외) = n 이면 해당 선수의 순위를 결정할 수 있다.

 

nwin+loss-1 == n인 선수의 수를 카운트하여 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int n, vector<vector<int>> results) {
    
    vector<vector<bool>> dp(n+1, vector<bool>(n+1, false));
    
    //floyd
    for (auto v : results) {
        int a = v[0];
        int b = v[1];
        dp[a][b] = true;
    }
    
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++)
            	//i가 k를 이기고 k가 j를 이기면 i는 j를 이긴다
                if (dp[i][k] && dp[k][j]) dp[i][j] = true;
        }
    }
    
    int cnt = 0;
    for (int i=1; i<=n; i++) {
        int nwin = 0;
        int nloss = 0;
        for (int j=1; j<=n; j++) {
            if (dp[i][j]) nwin++;
            if (dp[j][i]) nloss++;
        }
        if (nwin+nloss == n-1) cnt++;
    }
    return cnt;
}