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

그래프 탭에 있는 순위라는 문제

보자마자 예전에 백준에서 풀었던 역사라는 문제가 생각났다

역사 문제에서는 사건의 전후관계를 플루이드 워셜 알고리즘을 파악했었는데 여기서는 같은 원리로 승패를 파악했다

역사 문제 풀때도 이 알고리즘을 전후관계 파악에 쓰는게 되게 생각해내기 어렵다고 느꼈는데 이 문제에서 또 만나서 반가웠다

 

#include <string>
#include <vector>
 
using namespace std;
int player[105][105]; // player[i][j]==1 if player i beats player j
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    int len = results.size();
    for(int i = 0 ; i < len ; i++){
        int from = results[i][0];
        int to = results[i][1];
        player[from][to]=1;
        player[to][from]=-1;
    }
    for(int stopover = 1 ; stopover <= n ; stopover++){
        for(int from = 1 ; from <= n ; from++){
            for(int to = 1; to <= n ; to++){
                if(player[from][stopover]==1 && player[stopover][to]==1) player[from][to] = 1;
                else if(player[from][stopover]==-1 && player[stopover][to]==-1) player[from][to]=-1;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1; j <= n ;j++){
            if(i!=j && player[i][j]==0) break;
            if(j==n) answer++;
        }
    }
    return answer;
}

 

경유지를 설정하고 a가 b를 이기고 b가 c를 이긴다면 a가 c를 이긴다는 컨셉을 적용했다

마지막에는 자기 자신을 제외한 모든 선수들과의 승패가 결정된 사람의 수를 세어 return 해주었다

 

플루이드 워셜 알고리즘이 중간에 헷갈려서 가장 바깥 for 문을 경유지가 아니라 가장 안쪽으로 지정해주었더니 틀렸다고 나왔다

지금까지 플루이드 워셜을 쓸때 아무생각 없이 순서를 외워서 사용했었는데 이 기회에 좀 더 찾아보았다

나와 비슷한 궁금증을 가진 사람들의 질문이 은근 많았다

그 중에서 이해가 잘 되었던 풀이

stackoverflow.com/questions/65143864/does-rearranging-the-outerloop-in-floyd-warshall-algorithm-as-most-inner-loop-ch

Does rearranging the outerloop in Floyd-Warshall algorithm as most inner loop change the algorithm

 

플루이드 워셜에서 중요한 개념은 노드의 부분 집합을 늘려가면서 가장 빠른 경로를 찾는 것이니까 꼭 가장 바깥 for문에 경유지를 넣자!!