프로그래머스 : 순위 C++ (플로이드 와샬 활용)

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

풀이

1. 플로이드 와샬 다시 한번 복습했다, 굉장히 유용할거같다

ex) a->b 가 있고  b-> c 가 있다면 a->c 도 있다는거!!

 

2. 같은 의미로 a가 b를 이기고, b가 c를 이겼으면 a가 c를 이긴거나 마찬가지

 

3. 모두 정리 후에 다른 사람들 모두와의 상대전적이 남아있다면 그것의 순위를 알수있다는거!

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    int games[101][101]={0,};
    
    //1차 초기화
    for(int i=0;i<results.size();i++)
    {
        games[results[i][0]][results[i][1]] =1;
    }
    //플로이드 와샬
    //a: 중간 b: 시작 c: 도착지
    for(int a=1;a<=n;a++)
        for(int b=1;b<=n;b++)
            for(int c=1;c<=n;c++)
            {
                if(games[b][a] ==1 && games[a][c]==1)
                    games[b][c] =1;
            }
    
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            if(games[i][j]==1 || games[j][i]==1)
                cnt++;
        }
        
        if(cnt ==n-1)
            answer++;
    }
    
    return answer;
}