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

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49191

문제 난이도

Level 3

문제 접근법

격투 선수들의 등수가 정해져있다고 가정을 할 때, 4등이 있으면 1,2,3등에게 지고 5등에게는 이겨야한다.
1등은 나머지 사람들을 이겨야 확실한 순위라고 할 수 있다.
그렇기 때문에 해당 등수를 가질려면 N-1번의 승패를 알아야하고 A가 B를 이겼는데 B가 C를 이겼다면 A는 C를 이긴 게 된다.
마치 예제에서 4등한테 져서 5등이 된게 확실한 순위인 거처럼 연결고리가 있다.
그래서 우리는 최단 단위 거리를 갱신하는 플로이드-와샬 알고리즘을 사용한다.

통과 코드

#include <string>
#include <vector>

using namespace std;

bool ch[101][101];

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

피드백

어떻게 풀어야할지 모르겠어서 다른 사람 풀이를 참고했다. 플로이드-와샬을 이용한대서 완전 ???? 의외였다. 플로이드-와샬은 최단 거리를 알기 위할 때 사용하는 줄 알았는데 이런 문제에서도 응용될 수 있다는 점이 경이로웠다.