[프로그래머스] 순위

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> rank(n, vector<int>(n, 0));
    
    for(int i=0; i<results.size(); i++){
        rank[results[i][0]-1][results[i][1]-1] = 1;
    }
    
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (rank[i][k] == 1 && rank[k][j] == 1) {
                    rank[i][j] = 1;
                }
            }
        }
    }
    
    for(int i=0; i<n; i++){
        int count = 0;
        for(int j=0; j<n; j++){
            if(rank[i][j] == 1 || rank[j][i] == 1){
                count++;
            }
        }
        
        if(count == n -1){
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

경기 결과를 rank에 저장합니다.

rank[i][j] = 1은 i선수가 j선수에게 이겼다는 의미입니다.

1이 2를 이기고 2가 3을 이겼다면 1은 3을 이긴 것입니다.

모든 선수 쌍에 대하여 플로이드-와샬 알고리즘을 통해 중간 선수를 경유하여 승패 여부를 추가해야합니다.

최종적으로 업데이트 된 rank에서 다른 모든 선수와 승패 관계가 확정된 선수의 수를 카운팅합니다.

다른 모든 선수와 승패 관계가 확정된 선수는 순위를 확정지을 수 있으므로 answer을 증가합니다.

최종적으로 answer을 return 합니다.