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

출처: 프로그래머스 코딩테스트 연습: https://school.programmers.co.kr/learn/courses/30/lessons/49191

 

[문제풀이]
플로이드 와샬 알고리즘과 유사한 방법을 사용한다.
문제를 풀기전에 플로이드 와샬 알고리즘에 대한 정보를 보는것을 추천한다.
다익스트라와 달리 이차원배열을 이용한 동적계획법이라 볼 수 있다.

플로이드 와샬 알고리즘은 간선의 가중치의 비교를 통해서 
이차원 배열을 갱신하지만, 이 문제에서는 간선의 연결여부만을 통해서 
순위를 판별하기만 하면 된다.

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

using namespace std;

int MAX = 1000000;

int solution(int n, vector<vector<int>> results) {
    int answer = n;
    
    vector<vector<int>> A (n,vector<int>(n,MAX));
    
    //2차원배열 A 초기화
    for (int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(i == j){
                A[i][j] = 0;
            }
        }
    }
    
    //results에 있는 데이터 입력해주기
    for (auto res : results){
        A[res[0]-1][res[1]-1] = 1;
        A[res[1]-1][res[0]-1] = -1;
    }
    
    //플로이드 와샬의 변형
    for (int k = 0 ; k < n ; k++){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(A[i][k] == 1 && A[k][j] == 1){
                    A[i][j] = 1;
                    A[j][i] = -1;
                }
            }
        }
    }
    
    //정답 체크해주기
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(A[i][j] == MAX){
                answer -- ;
                break;
            }
        }
    }
    
    return answer;
}