순위

문제 링크

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

코딩테스트 연습 - 순위

 

문제 풀이

처음에는 다익스트라 문제인줄 알았으나 모든정점에서의 최단거리를 구하는 플로이드 와샬 알고리즘이 더 적합하다고 판단했다.

 

<핵심 아이디어>

플로이드와샬 알고리즘을 사용하며,

순위는 입력 간선과 출력간선의 합이 (전체노드 -1)일 때 결정된다. 

 

순위 결정법은 끄적거리다 발견했다..ㅋㅋ

 

 

문제 풀이 코드

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

using namespace std;

const int MN = 101;

bool fluid[MN][MN];

int solution(int n, vector<vector<int>> results) {
    
    int answer = 0;
    
    for(int i=0; i<results.size(); i++){
        int u=results[i][0];
        int v=results[i][1];
        fluid[u][v]=true;
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(fluid[i][k]&&fluid[k][j]) fluid[i][j]=1;
                
            }
        }
    }
        
    vector <int> cnt(n+1);
    
    for(int i=0; i<cnt.size(); i++){
        cnt[i]=0;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(fluid[i][j]==1){
                cnt[i]++; cnt[j]++;
            }
        }
    }
    
    for(int i=1; i<cnt.size(); i++){
        if(cnt[i]==(n-1)){
          answer++; 
        } 
    }
    
    return answer;

}