순서

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool vis[101][101];
// 정답 : 총 경기 횟수가 n-1이면 반드시 순위를 구할 수 있음!
// 플로이드 워셜 알고리즘
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(auto r : results) vis[r[0]][r[1]] = true;
    /* 플로이드 워셜 알고리즘 - */
    for(int k=1;k<=n;k++) // k는 중간다리 역할
        for(int a=1;a<=n;a++)
            for(int b=1;b<=n;b++)
                if(vis[a][k] and vis[k][b])
                    vis[a][b] = true;

    /* a가 b를 이겼거나 or b가 a를 이겼다면 cnt++
       즉, a가 참여한 총 경기가 n-1번이면 순위를 구할수 있는 것이 자명함! */
    for(int a=1;a<=n;a++)
    {
        int cnt=0;
        for(int b=1;b<=n;b++)
        {
            if(vis[a][b] or vis[b][a]) cnt++;
        }
        if(cnt == n-1) answer++;
    }
    return answer;
}

• 나의 시도들
  • 각 사람의 이긴 횟수를 구해서 반드시 승리하는 경우를 찾으려고 시도함 --> 실패
  • 모든 사람간의 승/패에 대한 표를 구했으나 확실히 순위를 정해진 사람의 조건을 찾지 못함 --> 실패

• 해답
  : 플로이드 워셜 알고리즘을 이용해 각 선수의 총 경기 횟수를 구하면 됨

• 정답 로직
  • 초기 입력시 배열 초기화 --> vis[A][B] = true : A선수가 B를 이긴 경우 true
  • 플로이드 워셜 알고리즘을 이용해서 A가 B를 이겼고 & B가 C를 이겼으면 = A가 C를 이긴 것 으로 갱신
  • 총 배열을 통해 A가 B를 이겼거나 or B가 A를 이긴 경우 = cnt증가
    즉, A가 한 경기 총 경기 횟수를 구할 수 있으며 이 값이 N-1이면 자명하게 순위를 구할 수 있음
    (왜냐하면 자신을 제외하고 모두와 경기를 했기 때문)