[틀림] 프로그래머스 순위 // 플로이드

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

프로그래머스

* 플로이드 학습

• 3중 for문으로
• 모든 정점 쌍의 최단거리를 구함
• O(n^3)

 

* 풀이

• 명제
  • i가 k를 이기고, k가 j를 이기면
  • i는 j를 이긴다.
  • j는 i에게 진다.
• 승부가 났는지 판단
  • 본인제외한 다른사람과 모두 승패를 겨루어 봤는지 확인( 표에 값이 채워져있어야함)

#include <bits/stdc++.h>

using namespace std;

int graph[104][104];
int ret;

int solution(int n, vector<vector<int>> results) {
    for( auto result : results){
        int a= result[0];
        int b= result[1];
        graph[a][b]=1; // a는 b를 이김
        graph[b][a]=-1; //b는 a에게 짐
    }
    
    //플로이드는 케이 아이 제이~
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(graph[i][k]==1 && graph[k][j]==1){
                    graph[i][j]=1;
                    graph[j][i]=-1;
                }
            }
        }
    }
    
    for(int i=1;i<=n;++i){
        int cnt=0;
        // 가로줄검사 a[i][0] ~ a[i][1] ...
        // 1번선수가 모두 승부가 났다면, 본인제외 값이 모두 채워져있을거임
        for(int j=1;j<=n;++j){
            if(graph[i][j]==1 || graph[i][j]==-1){
                cnt++;
            }
        }
        
        if(cnt==n-1) ret++;
    }
    
    
    return ret;
}