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

 이 문제는 이행적 폐포 (Transitive Closure) 를 이용해서 풀었다. 일단 이 문제에서 사람의 최대 수가 100명이므로 O(n^4) 알고리즘까지도 충분하다. 그리고 중요한 점은 경기 결과에 모순이 없다는 것인데, 이는 유향 그래프로 나타나지는 경기 결과에서 사이클이 없다는 소리와 같고, 이는 경기 결과에 대한 그래프가 DAG 임을 나타낸다는 것이다.

 

 

 처음에는 DAG 하면 위상 정렬이 떠올라 위상 정렬로 풀려고 했지만, 마땅한 방법이 떠오르지 않았다. 그러다가 incoming edge와 outcoming edge의 수를 더한 값이 n - 1이면 순위가 확실해진다는 규칙을 찾았고, 대학교 알고리즘 수업 때 배웠던 transitive closure가 생각났다. 이행적 폐포란 a -> b 이고 b -> c 이면 a -> c 인 연산을 모든 노드쌍에 대해 수행하는 것이다. 플로이드 워셜 알고리즘이 대표적으로 이행적 폐포를 이용해서 최단 경로를 찾는데, 이를 변형시켜서 문제를 해결할 수 있었다.  

 

 

 

#include <string>
#include <vector>

using namespace std;

#define MAX 100

bool edge[MAX + 1][MAX + 1];

void transitiveClosure(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (edge[i][k] && edge[k][j]) {
                    edge[i][j] = true;
                }
            }
        }
    }    
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for (vector<int>& result : results) {
        int win = result[0];
        int lose = result[1];
        edge[win][lose] = true;
    }
    
    transitiveClosure(n);
    
    for (int i = 1; i <= n; i++) {
        // win calculation
        int win = 0;
        for (int j = 1; j <= n; j++) {
            if (edge[i][j]) {
                win++;
            }
        }
        
        // lose calculation
        int lose = 0;
        for (int j = 1; j <= n; j++) {
            if (edge[j][i]) {
                lose++;
            }
        }
        
        if (win + lose == n - 1) {
            answer++;
        }
    }
    
    return answer;
}