[C++] 프로그래머스 순위 풀이(플로이드-워셜 알고리즘)

권투 선수들의 승패에 따른 순위를 매겨야 하는데 몇몇 경기 결과는 분실되었다. 

경기 결과를 확실하게 알 수 있는 선수들만이라도 추려보려고 하는데

순위를 정확하게 매길 수 있는 선수가 몇 명인지 구하는 문제 

 

---

문제의 조건

 

1. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 주어짐

 

2. results 배열의 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 뜻이다. 

 

3. 모든 경기 결과에는 모순이 없다. 

 

 

---

아직 그래프에는 많이 약하기 때문에 힌트를 봤는데 

플로이드-와샬 알고리즘을 이용하면 쉽게 풀린다고 해서 무엇인지 찾아보았습니다. 

 

 

플로이드-와샬 알고리즘

최단 거리를 구하는 그래프 알고리즘 중 하나

 

모든 쌍을 표현하는 행렬(2차원 배열)을 이용해서 다이나믹 프로그래밍 방식으로 각 정점간의 최단 거리를 업데이트 해 나가는 방식입니다.

 

어떤 정점을 거쳐 가는 것이 가장 짧은지 탐색하는 알고리즘으로,

어떤 정점을 거쳐 가는 거리가 그 정점과 직선으로 가는 것 보다 짧으면 어떤 정점을 거쳐 가는 거리로 업데이트 하면서 최단 거리를 찾는다

라고 할 수 있겠습니다. 

 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F 

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

자세한 설명은 위 블로그를 참조하십시오. 

 

---

풀이 과정

 

그러면 저 플로이드-와샬 알고리즘을 이용해서 어떻게 푸느냐!

아직 그래프엔 왕초보이기 때문에 플로이드-와샬 알고리즘이 어떤 건지 안다고 해도 문제를 바로 풀 수 있는 것은 아니었습니다.

그래서 또 풀이에 참조한 블로그

 

https://ansohxxn.github.io/algorithm/floyd/

(C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)

 

그림도 그려놓으셔서 이해에 도움이 됩니다. 

 

 

1. 각 선수들끼리의 경기 결과를 알아야 함

 

 

2. 1번을 알기 위해서 행렬(2차원 배열)을 선언할 필요가 있음

 

승패(True or False)	1번 선수	2번 선수
1번 선수	-	T
2번 선수	F	-

 

이렇게 정리해서 보면 1번 선수가 2번 선수한테는 이겼네

2번 선수가 1번 선수한테는 졌네 를 알 수 있습니다. 

이런 식으로 매개변수로 주어지는 n명의 선수들에 대한 bool 2차원 배열을 만듭니다. 

배열 인덱스는 0번부터 시작하지만 선수 번호는 1번부터 시작하기 때문에 

배열 인덱스와 선수 번호를 맞춰주기 위해 

n+1 x n+1 크기의 bool 2차원 배열을 선언한 후 false로 초기화 합니다. 

 

 

3. 매개변수로 주어지는 results를 이용해서 2번에서 만든 2차원 배열의 승리 정보를 1차로 갱신한다. 

 

예를 들어 [4,3] 은 4번 선수가 3번 선수를 이겼다는 뜻입니다. 

 

⬇️선수가 ➡️선수를 이겼다	1번 선수	2번 선수	3번 선수	4번 선수	5번 선수
1번 선수	F	F	F	F	F
2번 선수	F	F	F	F	F
3번 선수	F	F	F	F	F
4번 선수	F	F	T	F	F
5번 선수	F	F	F	F	F

 

처음엔 모두 false로 초기화 한 배열에서 4번 선수가 3번 선수를 이겼다는 표시를 하면 위와 같이 할 수 있을 것입니다. 

 

이런 식으로 승리 정보를 갱신합니다. 

 

 

4. 플로이드-와샬 알고리즘으로 i번 선수가 k번 선수를 거쳐서 j번 선수를 이길 수 있는지 확인한다. 

이길 수 있으면 해당 칸 true로 갱신 

 

 

5. 4번 과정을 거쳐 갱신된 결과를 바탕으로 순위를 매길 수 있는 선수의 수를 센다. 

나를 제외한 선수들에 대해서 승패를 확실하게 알 수 있으면 순위를 매길 수 있는 선수라는 뜻입니다. 

즉 확실하게 알 수 있는 승패가 n-1개인 선수라면 순위를 매길 수 있는 선수이기 때문에 정답 카운트에 포함시킵니다. 

 

---

소스 코드

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    vector<vector<bool>> matches(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; results.size() > i; i++)
        matches[results[i][0]][results[i][1]] = true;

    for (int k = 1; n >= k; k++) //현재 거쳐가는 선수 번호 
    {
        for (int i = 1; n >= i; i++) //i, j: 각각의 선수에 대한 승패 
        {
            for (int j = 1; n >= j; j++)
            {
                //k번 선수를 통해 승리를 확신할 수 있으면 true로 바꿔준다. 
                if (matches[i][k] && matches[k][j])
                    matches[i][j] = true;
            }
        }
    }

    int answer = 0;
    for (int i = 1; n >= i; i++)
    {
        int count = 0;
        for (int j = 1; n >= j; j++)
        {
            //각 선수끼리에 대한 경기결과가 true라면 승패가 확실하다는 뜻이니까 카운트 증가 
            //false면 알 수 없음 
            if (matches[i][j] || matches[j][i])
                count++;
        }

        //나를 제외한 선수들과의 경기결과가 확실하면 순위를 매길 수 있기 때문에
        //승패가 확실한 것의 갯수가 n-1개와 같으면 순위를 매길 수 있는 선수임 
        if (n - 1 == count)
            answer++;
    }

    return answer;
}