[프로그래머스 49191] 순위

문제풀이

 

무식한 풀이방법 밖에 떠오르지 않아. 풀이를 검색하여 풀었다.

 

플로이드-워셜  알고리즘을 활용한 문제이다.

 

1 - 2 의 순서를알고 2 -3 의 순서를 알때 1-3 의 순서도 알수 있다는 것을 체크하는 방식으로 플로이드 와샬 알고리즘을 사용한다.

 

플로이드-워셜 알고리즘은 그래프에서 정점끼리의 최단경로를 구하는 알고리즘 중 하나이다.

그리고 플로이드-워셜  알고리즘은 모든 경로를 구하는 방법이라 여기서 적용하기 좋은 문제였던것 같다.

 

나중에 따로 플로이드-워셜 알고리즘을 정리해볼 필요가 있는 것 같다.

 

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 99999999
using namespace std;
 
int score[101][101];
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            score[i][j] = MAX;
        }
    }
    
    for(int i=0;i<results.size();i++){
        int a = results[i][0];
        int b= results[i][1];
        score[a][b] = 1;
    }
     
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                score[i][j] = min(score[i][j],score[i][k]+score[k][j]);
            }
        }
    }
    
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            cout<<score[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    
    for( int i=1;i<=n;i++){
        bool check=true;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(score[i][j]==MAX && score[j][i] ==MAX){
                check = false;
                break;
            }
        }
        if(check)
            answer++;
    }
    
    return answer;
}
 
int main(){
    cout<<solution(5,{{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}})<<endl;
}
 

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49191