프로그래머스 - 순위

코드

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
bool graph[101][101];
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    memset(graph, false, sizeof(graph)); //cstring 헤더 추가
    for(int i=0; i<results.size(); i++)
    {
        int N1 = results[i][0];
        int N2 = results[i][1];
        graph[N1][N2] = true;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if (graph[i][k] && graph[k][j])
                    graph[i][j] = true;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
    for(int i=1; i<=n; i++)
    {
        int cnt = 0;
        for(int j=1; j<=n; j++)
        {
            if (graph[i][j] || graph[j][i]) //i가 j에게 이겼거나 졌거나 정보가 n-1개면 순위 예측할 수 있다.
                cnt++;
        }
        if (cnt == n - 1) answer++;
    }
    return answer;
}

플로이드 와샬 알고리즘을 사용했고, graph[i][j]가 true이면 i가 j를 이긴다는 의미로 사용하였다. 

directed graph이고, O(n^3)에 주어진 result에 따라 각 선수가 이기고 지는 정보에 대해서 구할 수 있다. 

if (graph[i][j] || graph[j][i]) 

                cnt++;

이 부분을 통해 결과의 정보가 n - 1개면 순위를 예상할 수 있기 때문에 answer++을 해준다.