[프로그래머스] 순위 (C++)

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

코딩테스트 연습 - 순위

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool floyd[101][101]={false,};

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for (auto r : results)
        floyd[r[0]][r[1]]=true;
    for (int k=1; k<=n; k++){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                if (floyd[i][k] && floyd[k][j])
                    floyd[i][j]=true;
            }
        }
    }
    for (int i=1; i<=n; i++){
        int cnt=0;
        for (int j=1; j<=n; j++){
            if (floyd[i][j] || floyd[j][i]){
                cnt++;
            }
        }
        if (cnt==n-1)
            answer++;
    }
    return answer;
}

개인적으로 아이디어를 떠올리기 어려운 문제였다.

 

floyd warshall 알고리즘을 이용해서, 승패를 가를 수 있는 경우를 따져주는게 포인트다.

a가 b를 이기면 floyd[a][b]=true, b가 c를 이기면 floyd[b][c]=true 이다.

 

이때 floyd-warshall 알고리즘을 이용해서 floyd[a][c]를 따져줄 때, floyd[a][b], floyd[b][c] (즉 b를 거치는 케이스) 가 모두 true이면 a가 c를 이긴다는 것이 성립되기 때문에 승패를 가를 수 있으므로, floyd[a][c]=true 해준다.

 

이런 식으로 모든 case에 대해 따져준 뒤, 한 명씩 체크해서 승패를 가를 수 있는 경우가 n-1가지이면(본인과 대결하는 경우는 빼준다), 순위를 가를 수 있는 애이므로 +1 해준다. 

 

이때 승패를 가를 수 있는 경우를 체크할 때 floyd[i][j] 외에도, floyd[j][i] 가 true인지도 같이 체크해주는 것이 중요하다.

 

자기 외에 다른 모든 사람에 대해 승패를 가를 수 있는 경우일 때, 순위를 따질 수 있는 것이다.