[Programmers]그래프 > 순위(c++)

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

코딩테스트 연습 - 순위

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 을 응용해서 풀었다.

 

1. floyd의 초깃값을 모두 -1로 초기화

2. result[i][0]는 이긴 선수, result[i][1]는 패배한 선수 이므로 floyd에서 가로를 기준으로, 자신이 이겼는지 졌는지를 나타낸다.

예시의 results[0][0] = 4, results[0][1] = 3 에서 4가 3을 이겼으므로

floyd[results[i][0]][results[i][1]] =1, floyd[results[i][1]][results[i][0]] = 0

3. floyd알고리즘을 응용해서, floyd[i][j]에서 i가 이긴선수, j가 진 선수 이므로

j기준으로 볼때 자신을 이긴 선수가(=i) 1일때, (floyd[i][j] == 1) 다른 선수에게 패배했다면 당연히 자신도 패배한다.

(floyd[i][k] == 0 다른선수에게 패배, floyd[j][k] = 0 자신도 패배.)

4. floyd[j][k] = 0라면 반대로 floyd[k][j] = 1 도 성립한다.

5. 사용하지 않는 0와 자기자신을 제외한 ㅡ 모든 선수들과의 경기 결과를 알 수 있다면 (floyd[i]의 -1개수가 2라면) answer++   

 

---

main포함 코드

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<int>> floyd(n+1, vector<int>(n+1,-1));
    
    for(int i=0;i<results.size();i++){
        for(int j=0;j<results[i].size();j++){
            floyd[results[i][0]][results[i][1]] = 1;
            floyd[results[i][1]][results[i][0]] = 0;
        }
    }
    
    for(int i=1;i<n+1;i++){
        for(int j=1;j<n+1;j++){
            if(floyd[i][j] == 1){
                for(int k=1;k<n+1;k++){
                    //자신을 이긴 곳이, 다른 곳에게 패배(0) 라면 자신도 (0)
                    if(floyd[i][k] == 0) { floyd[j][k] = 0; floyd[k][j] = 1; }
                }
            }
        }
    }
    
    for(int i=1;i<n+1;i++)if(count(floyd[i].begin(), floyd[i].end(), -1) == 2)answer++;
    return answer;
}
int main(){
    
    int n = 4;
//    vector<vector<int>> results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
    vector<vector<int>> results = {{1, 2}, {2, 3}, {1, 4}};
    solution(n, results);
    return 0;
}

 

---

사용한 테스트케이스

4  /  [[1, 2], [2, 3], [1, 4]]  Return 1