[프로그래머스] 순위

문제요약

1. 씨름 선수들 간의 싸움 데이터 벡터가 주어집니다. 하나의 싸움 데이터는 [이긴사람,진사람]으로 구성돼 있습니다.
2. 선수들 간의 실력 순위는 사실 1등부터 꼴등까지 정해져있으며 싸우면 순위가 높은 사람이 무조건 이깁니다.
3. 코치가 싸움데이터들의 일부를 유실했습니다. 남아있는 데이터로 순위가 몇등인지 정확하게 알 수 있는 선수들의 수를 구하세요.

아이디어

그래프라는 태그가 적혀있어서 플로이드 워셜문제라는 힌트를 얻었던것같다..
n:n shortest path를 구한 후 한 선수에 대해 나머지 선수들에 대한 거리 dm(거리는 이길 수 있다면 +몇사람, 질거라면 -몇사람으로 표현될 것이다.)가 다 구해져있으면 이 선수의 순위가 정확하게 매겨질 것이라 생각했다.
근데 -거리는 플로이드 워셜 알고리즘으로 구할 수 없으므로 edge를 reverse 시킨 rg를 선언하여 거리 rdm을 구하고 dm이나 rdm이 채워져있다면 몇위차인지 알 수 있다고 판단했다.

참고로 플로이드 워셜 알고리즘을 참조했다

플로이드 워셜을 벌써 까먹은 방년 23세 라클님^^..

삽질

1. 요즘 2차원 배열을 파라미터로 bool g[101][101]과 같이 사이즈를 2차원으로 지정할 수 있다는 것을 알게된 후 애용하고 있는데 리턴형은 그렇게 리턴할 수 없다는 걸 알게 되었다
2. 1주전만해도 삼성 기출 풀면서 배열 copy는 확실히 외웠다고 생각했는데 쓰는 방법을 또 까먹었었다^^^

코드

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
int d[101][101];

int INF = 99;
void calc_component(int n,bool g[101][101]){//플로이드 워셜로 n:n거리
    for(int i = 1;i<=n;i++){
        for(int j =1;j<=n;j++){
            if(g[i][j]) d[i][j] = 1;
            else d[i][j] = INF;
        }
    }

    for(int k = 1;k<=n;k++){
        for(int i = 1;i<=n;i++){
            for(int j =1;j<=n;j++){
                if(d[i][k]+d[k][j]<d[i][j]){
                    d[i][j] = d[i][k]+d[k][j];
                }
            }
        }
    }
}


int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    
    bool g[101][101];//100*100
    bool rg[101][101];
    for(int i = 0;i<results.size();i++){
        int a = results[i][0],b = results[i][1];
        g[a][b] = 1;
        rg[b][a] = 1;
    }
    calc_component(n,g);
    int dm[101][101];
    copy(&d[0][0],&d[0][0]+101*101,&dm[0][0]);
    
    calc_component(n,rg);
    int rdm[101][101];
    copy(&d[0][0],&d[0][0]+101*101,&rdm[0][0]);
    
    for(int i = 1;i<=n;i++){
        bool cert = true;
        for(int j = 1;j<=n;j++){
            if(j == i){
                continue;
            }
            if((dm[i][j]!=INF&&rdm[i][j]==INF)||(dm[i][j]==INF&&rdm[i][j]!=INF)){
                continue;
            }
            else{
                //cout<<i<<","<<j<<","<<dm[i][j]<<" "<<rdm[i][j]<<endl;
                cert = false;
                break;
            }
        }
        if(cert){
            answer++;
        }
    }
    return answer;
}