[프로그래머스] Level 3. 순위

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

프로그래머스

 

 

플로이드-워셜 알고리즘

 

승패정보가 전파된다. for문을 3번 사용하여 a -> b를 이기고 b->c 를 이겼을 경우, a->c 를 이겼음 처리를 해준다. 

최단거리 찾는 문제에 보통 사용되는데,  핵심은 삼중for문을 사용하는것이다

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> table (n+1, vector<int>(n+1,0)); //0 모름 1 이김 -1 짐
    for(int i=0; i<results.size(); i++){
        table[results[i][0]][results[i][1]] = 1;
        table[results[i][1]][results[i][0]] = -1;
    }
    
    // **Floyd-Warshall 알고리즘 적용**
    for (int k = 1; k <= n; k++) { // 중간 경유 선수
        for (int i = 1; i <= n; i++) { // 출발 선수
            for (int j = 1; j <= n; j++) { // 도착 선수
                if (table[i][k] == 1 && table[k][j] == 1) { 
                    table[i][j] = 1; // i가 k를 이기고, k가 j를 이기면 i가 j를 이김
                    table[j][i] = -1; // j는 i에게 패배
                }
                if (table[i][k] == -1 && table[k][j] == -1) {
                    table[i][j] = -1; // i가 k에게 지고, k가 j에게 지면 i도 j에게 짐
                    table[j][i] = 1; // j는 i를 이김
                }
            }
        }
    }

    
    for(int player = 1; player <=n ; player++){
        answer++;
        for(int i=1; i<=n; i++){
            if(player != i  && table[player][i] == 0){
                answer--; break; //결과모름
            }
        }
    }
    return answer;
}