#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool vis[101][101];
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++)
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;
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
이면 자명하게 순위를 구할 수 있음
(왜냐하면 자신을 제외하고 모두
와 경기
를 했기 때문)