프로그래머스. 순위(c++) / 그래프+플로이드와샬

처음에는 어떻게 풀어야할지 도통 감이 오지 않아서,,, 결국 질문하기 탭에서 힌트를 얻었다.

플로이드 와샬을 통해 풀수 있었다.

일반적으로 플로이드 와샬은 최단 경로를 구하기 위해 사용하지만

이 문제에서는 단지, 이기는지 지는지의 관계에 초점을 맞추어서 플로이드 와샬을 적용시켰다.

만약, dp[a][b]=1이라면 a가 b를 이기는 관계이고 dp[a][b] = -1이라면 a가 b에게 지는 관계이다.

그리고 문제에 따라, a가 b를 이기고 b가 c를 이긴다면? a가 c를 이기는 것이 성립한다는 것을 알 수 있다.

위의 논리대로 플로이드와샬을 활용해 로직을 구현하면 된다.

 

#include <string>
#include <vector>
#include <climits>
#include <iostream>
 
using namespace std;
 
int dp[102][102] = {0, }; // i가 j를 이기면 1, 지면 -1, 모르면 0
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i=0; i<results.size(); i++){
        int win = results[i][0];
        int lose = results[i][1];
        
        dp[win][lose] = 1;
        dp[lose][win] = -1;
    }
    
    // 시작 점
    for(int i=1; i<=n; i++){
        // 거쳐가는 점
        for(int j=1; j<=n; j++){
            // 끝점
            for(int k=1; k<=n; k++){
                if(dp[i][j]==1 && dp[j][k]==1){
                    dp[i][k] = 1;
                    dp[k][i] = -1;
                }
                if(dp[i][j]==-1 && dp[j][k]==-1){
                    dp[i][k] = -1;
                    dp[k][i] = 1;
                }
            }
        }
    }
    
    for(int i=1; i<=n; i++){
        int num = 0;
        for(int j=1; j<=n; j++){
            if(dp[i][j]==0){
                num++;
            }
        }
        if(num==1){
            answer++;
        }
    }
    
    return answer;
}