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

플로이드 와샬 알고리즘을 이용해서 풀었다.

자세한 방법은 아래의 블로그에서 공부해보면 좋을 것 같다.

[알고리즘] 플로이드 와샬 (Floyd Warshall)

 

플로이드 와샬 알고리즘은 A 노드에서 B 노드로 가는 가장 최소한의 길이를 구하는 방법에 사용되는데 거쳐가는 노드를 이용해서 최소한의 길이를 구하는 방법이다.

 

이 플로이드 와샬 알고리즘의 개념은 어떤 식으로 문제에 대입해서 결과를 도출해내는 것일까?

 

만약에 A와 B의 관계를 알고 싶다. 하지만 A,C의 관계 정보 C, B의 정보를 안다면 A, B의 정보를 추론을 할 수 있다. 예를 들어 A가 C를 이기고 C가 B를 이기면 A는 B를 이긴다는 것을 알 수 있다. 이렇게 C는 거쳐가는 노드이고 C는 A, B를 이어주는 존재가 되는 것이다.

 

따라서 모든 거쳐가는 노드를 탐색하면서 이어줄 수 있는 부분은 이어주면 마지막에는 모든 결과값을 얻을 수 있을 것이다.

 

arr[시작][끝]에 노드끼리의 관계를 저장을 할 것이고 정의가 안되어있으면 -1, 이기면 1, 지면 0이다. 나는 이렇게 했지만 서로 승부만 정할 수 있는 것만 알 수 있으면 되기 때문에 true,false로 관계를 나타내도 좋다.

 

그래서 3중 for문에서 arr[i][k] == 1 && arr[k][j] == 1 또는 arr[i][k] == 0 && arr[k][j] == 0을 체크하면서 거쳐가는 노드로 인해서 시작과 끝이 연결될 수 있는지 체크를 한다.

 

3중 for문이 끝나고 나면 arr에 시작과 끝의 관계가 정의되어있는지에 대한 정보가 남게 된다.

 

그러면 순위를 정할 수 있는 것은 어떻게 알 수 있는까? 그것은 자신 이외의 모든 노드와의 관계를 정의할 수 있다면 순위를 알수있다.

 

즉 4는 1,2,3한테 지고 5한테 이기는 것을 알기 때문에 순위를 알 수 있는 것이다.

 

주의 : 플로이드 와샬 알고리즘 3중 for문을 사용해야하는데 이때 for 문의 순서가 중요하다. 첫번째는 거쳐가는 노드을 나타내고 두번째는 시작 노드, 세번째는 도착 노드이다. (N의 최대값은 100이다. 그래서 n^3 = 1000000이기 때문에 시간복잡도는 통과를 할 것이다.)

 

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int arr[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
        
    memset(arr, -1, sizeof(arr));
    for (auto re : results){
        int win = re[0];
        int lose = re[1];
        arr[win][lose] = 1;
        arr[lose][win] = 0;
    }

    for (int k = 1; k <= n; k++){ // 거쳐가는 노드
        for (int i = 1; i <= n; i++){ // 시작 노드
            for (int j = 1; j <= n; j++){ // 끝 노드
                if (arr[i][j] != -1)
                    continue;
                if (arr[i][k] == 1 && arr[k][j] == 1)
                    arr[i][j] = 1;
                if (arr[i][k] == 0 && arr[k][j] == 0)
                    arr[i][j] = 0;
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        int pass = 0;
        for (int k = 1; k <= n; k++){
            if (arr[i][k] == -1){
                pass++;
            }
        }
        if (pass == 1) // 자기 자신에서 자신한테 가는 길은 없어서 -1로 남는다. 즉 -1개수가 1개인 경우 순위를 알 수 있다.
            answer++;
    }
    
    return answer;
}