순위 - C++

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

선수의 수는 1명 이상 100명 이하입니다.
경기 결과는 1개 이상 4,500개 이하입니다.
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.

문제 풀이

개인적으로 아주 어려웠던 것 같다. 결과적으로 인터넷에 검색을 통해 알게 되었는데, 그 과정을 설명하자면 먼저 연습장에 한번 작은 것 부터 한번 직접 해봤었다.

거기서 나온 알고리즘은 게임의 승패를 알 수 있는 경기가 n-1개 이면 확실히 순위를 알 수 있었다. 그런데 위의 예시처럼 5는 2와 1번 밖에 시합을 하지 않았지만 꼴등이라는 명확한 순위를 알 수 있기에 어떻게 해야할지 고민을 해봤지만 스스로 답을 낼 수 없었다.

그래서 검색을 하니 플로이드-와샬 알고리즘을 사용한다고 해서 띠용??했다 ㅋㅋㅋ 플로이드 와샬 알고리즘은 최단거리를 알기 위한 알고리즘 아니었나? 해서 다시한번 공부하고 정리해 보도록 하자.

플로이드 와샬 알고리즘

이전 문제에서 그래프 문제 유형별로 사용하는 알고리즘을 정리했는데, 그 중 플로이드 와샬은 모든 정점에서 모든 정점으로 가는 최단 경로를 찾을 때 쓰는 알고리즘이다. 다른 알고리즘에 비해 거쳐가는 정점을 기준으로 알고리즘을 수행하는데,
예를 들어, 1->3 까지 바로 가는 비용이 8이라면, 1->2-> 3 비용이 8보다 작다면 1 -> 3 비용을 갱신하는 알고리즘이다. 즉

X에서 Y로 가는 최소비용 vs X에서 Z노드를 거쳐 Y로 가는 비용

//k = 거쳐가는 노드
for(int k = 0 ; k < n ; k++)
{
	//i = 출발 노드
    for(int i = 0; i<n ; i++)
    {
    	//j = 도착 노드
        for(int j = 0; j < n ; j++)
        {
        	if(node[i][k] + node[k][j] < node[i][j])
            	node[i][j] = node[i][k] + node[k][j];
        }
    }
}

플로이드 와샬 알고리즘을 살펴봐도 이 문제에서 이 알고리즘을 사용하는 이유를 잘 모르겠다...😥
그러는 와중에 그나마 이해를 한게 이 알고리즘은 1,2,3,4,5의 선수가 있을 때, 1과 2의 단순한 하나의 경로(경기)로 취급하는게 아니라, 1이 지금까지 거쳐온 노드(상대 선수)와의 경로(경기)를 통해 2와의 승부에 임하는 것이다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool>> res(n+1,vector<bool>(n+1,false));
    
    for(int i = 0 ; i < results.size(); i ++)
    {
        int winner = results[i][0];
        int loser = results[i][1];
        res[winner][loser] = true;
    }
    
    for(int k = 1; k < n+1 ; k++)
    {
        for(int i = 1; i < n+1; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                if(res[i][k] && res[k][j])
                    res[i][j] = true;
            }
        }
    }
    
    for(int i = 1; i < n +1 ; i ++)
    {
        int cnt = 0;
        for (int j = 1; j < n+1 ; j ++)
        {
            if(res[i][j] || res[j][i])
                cnt++;
        }
        if (cnt == n-1)
            answer ++;
        
    }
    
    return answer;
}