순위 [Lv. 3]

프로그래머스

N명의 권투선수가 참여한 권투 대회, 심판은 경기 결과를 가지고 순위를 매기려하는데 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없는 상황입니다. 남아있는 결과를 통해 순위를 확실히 알 수 있는 사람이 몇명인지 찾아주세요.

(A선수가 B선수를 이기고 B선수가 C선수를 이기면 A선수는 무조건 C선수를 이깁니다)

 

풀이방법

플로이드-워샬 알고리즘을 사용하여 풀 수 있겠습니다. 순위라고 생각하지 않고 길찾기라고 생각하면 쉽습니다.

A선수와 모든 선수와의 결과를 알 수 있다면 A선수는 순위를 명확히 확인할 수 있습니다. 바꿔서 생각하면

A지점에서부터 모든 지점으로 길찾기가 가능한지를 찾으면 되겠죠.

 

대결 결과를 담을 2차원 배열을 만들어주고

array[A선수][B선수] = A선수가 이겼다면 1, 졌다면 -1;

위와 같이 초기값을 설정해줍니다.

 

---

A선수가 B선수를 이기고 B선수가 C선수를 이겼다면 A선수는 C선수를 이길 수 있습니다. 반대로, 

A선수가 B선수에게 이고 B선수가 C선수에게 졌다면 A선수는 C선수에게 이길 수 없습니다.

 

다른 상황으로

A선수가 B선수를 이기고 B선수가 C선수에게 졌다면 A선수와 C선수의 결과는 알 수 없습니다. 반대로,

A선수가 B선수에게 지고 B선수가 C선수에게 이겼다면 A선수와 C선수의 결과는 알 수 없습니다. 

---

즉 플로이드-워셜에서 길찾기가 가능한 부분은 A > B && B > C 이거나 A < B && B < C 일 때 입니다.

 

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    vector<vector<int>> v(n, vector<int>(n, 0));
    
    for(auto& result : results)
    {
        v[result[0]-1][result[1]-1] = 1;
        v[result[1]-1][result[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 (v[i][k] != 0 && v[i][k] == v[k][j])
                    v[i][j] = v[i][k];
            }
        }
    }
    
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if (v[i][j] == 0)
                cnt++;
        }
        if (cnt == 1)
            answer++;
    }
    return answer;
}