[프로그래머스] 순위 [C++][lv.3] 코딩테스트 고득점 Kit

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

프로그래머스

 

 

#문제 간단 정리

 

플로이드 워셜을 사용

 

 

#문제 해결 방법

 

기본적으로 플로이드 워셜을 사용한다.

플로이드-워셜 알고리즘을 잘 모른다면 

https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘

 

를 참고해서 확인하고 오도록 하자

 

 

기본적으로 플로이드 워셜은 모든 노드에 대한 최단거리를 갱신하는데 (N^3)

이어져 있지 않은 노드라면 INF 로 남아있게 된다

 

즉 플로이드 워셜을 사용한 후

INF 로 남아있는 거리가 있는지 확인하고

그 노드는 순위를 확인 할 수 없는 노드이다.

 

 

 

#전체 코드

#include <vector>
#include <queue>
#include <climits>


using namespace std;
int solution(int n, vector<vector<int>> results) {
    const int INF = 1000000000;
    vector<vector<int>> nodes (n+1, vector<int>(n+1,INF));
    
    for(int i=1; i<=n; i++){
        nodes[i][i] = 0;
    }
    for(auto result : results){
        nodes[result[0]][result[1]] = 1;
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
               if(nodes[i][j] > nodes[i][k] + nodes[k][j]){
                   nodes[i][j] = nodes[i][k]+nodes[k][j];
               } 
            }
        }
    }
    
    
    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        bool flag = true;
        for (int j = 1; j <= n; ++j) {
            if (i != j && (nodes[i][j] == INF && nodes[j][i] == INF)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            answer++;
        }
        
    }
    return answer;
}