프로그래머스 - 순위 - C++

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

프로그래머스

 

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer=0;
    
    vector<unordered_set<int>> wins(n+1);
    vector<unordered_set<int>> loses(n+1);
    
    for(auto& item : results)
    {
        // wins[n] : n 이 이긴 선수목록
        wins[item[0]].insert(item[1]);
        // loses[n] : n 을 이긴 선수목록
        loses[item[1]].insert(item[0]);
    }
    
    for(int i=1;i<=n;i++)
    {
        // n 이 이긴선수는 n을 이긴 선수모두도 이긴것으로 간주
        for(int c : loses[i])wins[c].insert(wins[i].begin(),wins[i].end());
        // n이 패배한 선수를 이긴 선수들을 n도 이겼다고 간주
        for(int c : wins[i])loses[c].insert(loses[i].begin(),loses[i].end());
    }
    
    for(int i=1;i<=n;i++)
    {
        if(wins[i].size()+loses[i].size()==n-1)
            answer++;
    }
    
    return answer;
}

경기 결과가 results 2차원 벡터에 주어지는데 이를 통해 순위를 유추가능한 선수의 수를 리턴하는 문제이다. 

따라서 최대한 많은 정보를 만들어야하는데 

먼저 기존 정보를 wins, loses에 저장한다. 

wins[i]는 i가 이긴 선수의 목록이다. 

loses[i]는 i를 이긴 선수의 목록이다. 

 

vector<unordered_set<int>> wins(n+1);
    vector<unordered_set<int>> loses(n+1);
    
    for(auto& item : results)
    {
        // wins[n] : n 이 이긴 선수목록
        wins[item[0]].insert(item[1]);
        // loses[n] : n 을 이긴 선수목록
        loses[item[1]].insert(item[0]);
    }

 

그 후, 주어진 정보를 가지고 유추가능한 정보를 추출해야하는데 삼단논법을 활용한다.

a win b, b win c 이면 a win c 이므로 wins[a]에 c를 넣는 과정이다.

마찬가지로 loses[c]에 a도 넣어야한다. 

 

for(int i=1;i<=n;i++)
    {
        // n 이 이긴선수는 n을 이긴 선수모두도 이긴것으로 간주
        for(int c : loses[i])wins[c].insert(wins[i].begin(),wins[i].end());
        // n이 패배한 선수를 이긴 선수들을 n도 이겼다고 간주
        for(int c : wins[i])loses[c].insert(loses[i].begin(),loses[i].end());
    }

loses[i]의 모든 선수에 대해서 즉, i가 패배한 모든 선수에 대해서 i가 이긴 선수의 목록을 추가한다. 

또한, wins[i]의 모든 선수에 대해서 즉, i가 승리한 모든 선수에 대해서 i가 패배한 모든 선수의 목록을 추가한다. 

 

이 과정을 for문을 돌며 추가한다. 

 

for(int i=1;i<=n;i++)
    {
        if(wins[i].size()+loses[i].size()==n-1)
            answer++;
    }

마지막으로 얻은 정보에 대해서 i가 이긴사람의 수 + i가 진 사람의 수를 합쳤을 때 n-1 이면 모든 선수에 대해서 경기결과를 다 아는 것이기 때문에 순위를 알 수 있다. 따라서 answer을 증가시킨다. 

 

wins[i]에 포함된 선수면 loses[i]에 포함될수 없기때문에 합의 결과는 n-1을 넘길수 없다. 

 

여기서 근데 한가지 의문이 생긴다. 

반복문을 한번 돌며 정보를 가공했는데 만약 a라는 정보를 얻기위해서는 b라는 정보가 필요한데, 

b라는 정보는 반복문의 n-1번째에 만들어진다면 반복문을 한번 더 돌렸을 때, 답이 달라지게 된다.

 

따라서 반복문을 한번만 돌려서 얻은 이 코드는 반쪽자리 정답이라 할 수 있다.

이 경우에 플로이드-워샬 알고리즘을 써야한다고 한다. 

 

간단하게 그래프의 모든 노드에 대해서 최단경로를 찾는 알고리즘이다. 

이 알고리즘을 통해 각 경로를 i와 j의 연관성이라고 보면 된다. 

 

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer=0;
    
    vector<vector<int>> dist(n+1,vector<int>(n+1,1e9));
    
    for(auto& item : results)
        dist[item[0]][item[1]]=1;
    
    for(int i=1;i<=n;i++)
        dist[i][i]=0;
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j] = dist[i][k]+dist[k][j];
            
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(dist[i][j]<1e9||dist[j][i]<1e9)cnt++;
        }
        if(cnt==n-1)answer++;
    }
    
    return answer;
}

dist 라는 2차원 벡터를 만들고 1e9로 초기화한다. (1e9는 10억이다.)

주어진 결과와 자기자신에게로 가는 값을 초기화한다. 

 

for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j] = dist[i][k]+dist[k][j];

플로이드-워셜 알고리즘이다. 

i->j 로 가는 경로에 i->k + k->j 가 더 짧다면 업데이트한다. 

모든 k에 대해서 모든 i->j를 따져서 업데이트한다. 

 

for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(dist[i][j]<1e9||dist[j][i]<1e9)cnt++;
        }
        if(cnt==n-1)answer++;
    }

플레이어 수를 계산한다. 

이 때, dist[i][j] < 1e9 인 이유는 간접적인 관계의 경우 2,3으로 늘어날 수 있기 때문이다. 

 

이걸 봤을 때도 k에 대해서 한번만 for문을 반복하기 때문에 아까랑 같은 문제가 발생하는 것은 아닌지 의문이 생겼다. 

 

chat gpt에게 물어봤는데 그래도 뭔가 이해가 되지않는다. 

어쨋든 순서에 상관없이 결과적으로 모든 경로가 최단경로로 업데이트 된다고 한다. 

아직 많이써보지않아서 동작방식이 제대로 습득되지 않았을 수도 있으니 앞으로 계속 써보면 자연스레 체득될것이라 생각한다.