프로그래머스 순위 문제

문제와 제한 사항은 위와 같습니다.

 

처음으로 참여했던 알고리즘 스터디에서 나온 문제인데, 플로이드 와샬 알고리즘을 활용해서 풀 수 있습니다. 해당 알고리즘은 각 정점의 노드 간 최단 거리는 구하는 알고리즘입니다.

 

해당 알고리즘에 대해서 이해하려고 할 때 추천하는 영상입니다. 만약 이 영상을 보고 풀 수 있다면 풀어보고, 코드를 보려는 분들은 맨 아래에 정답 코드를 활용하시면 됩니다.

 

문제 정답

/**
 * 순위 문제
 * 권투선수들의 순위를 구할 수 있는 선수의 수를 리턴(선수 100명 이하, 경기결과 4500개 이하)
*/
#include <bits/stdc++.h>
using namespace std;
bool a[101][101]; // 승리 여부 표시

int solution(int n, vector<vector<int>> results){
    int answer = 0;

    // 승리 결과에 따라 표시하기
    for(int i=0; i<results.size(); i++){
        a[results[i][0]][results[i][1]] = true;
    }

	// 바로 가는 노드는 없더라도 거쳐서 갈 수 있는지
    for(int k=1; k<=n; k++) { // 중간노드
        for(int i=1; i<=n; i++) { // 시작노드
            for(int j=1; j<=n; j++) { // 도착노드
                if(a[i][j] && a[j][k]) {
                    a[i][k] = true;
                }
            }
        }
    }

    // i선수의 결과를 알 수 있는지 여부
    // 본인제외 모두 경기를 했다면 이겼든 졌든
    // 순위를 알 수 있기 때문에 answer++
    for(int i=1; i<=n; i++) { 
        int count = 0;
        for(int j=1; j<=n; j++) {
            if(a[i][j] || a[j][i]) {
                count++;
            }
        }

        if(count == n-1) { // count가 n-1이라면 모두와 경기했다는 것
            answer++;
        }
    }

    return answer;
}