[프로그래머스] 순위 / 플로이드-워셜 알고리즘 / C++ 풀이

문제 링크

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

프로그래머스

 

풀이 전략

문제에 따르면 실력이 더 좋은 선수가 항상 이긴다고 한다. 예를 들어, A가 B를 이기고 B가 C를 이긴다면, A는 항상 C를 이긴다. 이를 그래프로 표현한다면 A에서 B로 가는 경로가 있다면 A에서 C로 가는 경로가 있다고 표현할 수 있다. 다시 말해 B를 중간 경로로 하여 A에서 C로 갈 수 있는 것이다. 그래프에서 '갈 수 있다'는 것은 곧 '이긴다'는 의미가 된다.

 

플로이드-워셜 알고리즘을 이용해 이 문제를 풀 수 있다. 플로이드-워셜 알고리즘은 모든 노드 쌍에 대한 최단 경로를 알아낼 수 있다. 이 문제에서 최단 경로는 '승패 확인 가능 여부' 이다. 일반적으로 플로이드-워셜 알고리즘에서 최단 거리는 시작 노드 S, 도착 노드 E, 중간 노드 M에 대해 A[S][E]  = min(A[S][E], A[S][M] + A[M][E]) 로 갱신한다. 하지만 이 문제에서는 승패 여부 판단 가능 여부(true 또는 false)로 갱신하면 된다. 

 

플로이드-워셜 알고리즘 수행 이후 인접 행렬 A를 보면 모든 선수 쌍에 대한 경기 결과를 알 수 있다. A[x][y]가 true 라면 x는 반드시 y를 이긴다. A[x][y]가 true가 아니라면 x와 y의 경기 결과는 이를 통해 알 수 없다. 하지만 A[x][y]가 true가 아님에도 A[y][x]가 true라면, y는 항상 x에 이긴다는 의미로 x와 y의 경기 결과를 확정할 수 있다.

 

C++ 코드

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    bool A[101][101] = {false,};
    
    /*인접행렬로 표현 : A[x][y] == 1 "x는 y를 이김"*/
    for(const auto& r : results) {
        A[r[0]][r[1]] = true; //winner - loser
    }
    
    /*Floyd-warshall*/
    for(int k = 1; k <= n; ++k) {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(A[i][k] == true && A[k][j] == true) {
                    A[i][j] = true;
                }
            }
        }
    }
    
    /*
    승패 확정 여부 확인, 모든 상대 선수에 대해 승패 여부를 알 수 있어야 함
    */
    for(int a = 1; a <= n; ++a) {
        bool flag = true;
        for(int b = 1; b <= n; ++b) {
            if(a==b) {continue;}
            if(A[a][b] == false && A[b][a] == false) {
                flag = false;
                break;
            }
        }
        
        if(flag == true) {
            answer++;
        }
    }
    return answer;
}