[C++] 프로그래머스 순위

🌽 문제

🥔 풀이

1. 승패 정보를 2차원 그래프에 저장
2. 플로이드-워셜 알고리즘으로 간접 승패 처리
3. 각 선수마다 승패 총합이 n-1이면 순위 확정 가능
4. 조건 만족하는 선수 수를 세어 반환

🥬 코드

#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    vector<vector<bool>> win(n + 1, vector<bool>(n + 1, false));
    for (const auto& result : results) {
        int w = result[0];
        int l = result[1];
        win[w][l] = true;
    }
    
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (win[i][k] && win[k][j]) {
                    win[i][j] = true;
                }
            }
        }
    }
    
    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            if (win[i][j] || win[j][i]) cnt++;
        }
        if (cnt == n - 1) answer++;
    }
    
    return answer;
}

🥜 채점