[C++/PGS] Lv.3 : 순위 (그래프/Floyd-Warshall)

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

 

문제 설명

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

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

 

제한사항

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

---

삽질

 

그래프는 그냥 다 bfs나 dfs로 풀면 돠ㅣ는줄 알았던 사람 나야나...나야 나....😩

그냥 삽질하다가 어떻게 푸나 싶어서 질문 게시판 들어가보니

"플로이드 와샬" 알고리즘을 써서 풀어야 한다고 한다.

그게뭔데요..,

 

플로이드-워셜 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.
알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이를 찾는다.

 

그러니까 단순하게 말하면

a가 b로 가고, b는 c로 간다면 결과적으로 a는 c로 가는 것이다.

이를 이용한 탐색법이었음

 

그래서 일단 matrix를 만든 후 승부를 알 수 있는 경우들을 플로이드 와샬을 적용하여 모두 1로 바꾼다.

(a가 b를 이기고, b가 c를 이겼다면 a가 c를 이길 것이므로)

 

이후 승부 횟수를 세어서, 총 n-1번의 승부를 한 선수는 순위가 확정되므로 정답 처리를 해주면 완성...!

 

 

 

나의 풀이

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

bool mat[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(int i=0; i<results.size();i++){
        mat[results[i][0]][results[i][1]] = true;
    } // 매트릭스 그래프 만들기

    for(int k=1; k<=n;k++){
        for(int i=1; i<=n;i++){
            for(int j=1; j<=n; j++){
                if(mat[i][k] && mat[k][j]){ // i가 k를 이기고, k는 j를 이겼을 때
                    mat[i][j] =true; // i는 j를 이길 것임
                }
            }
        }
    }
    for(int i=1; i<=n;i++){
        int count =0;
        for(int j=1; j<=n;j++){
            if(mat[i][j] || mat[j][i]){ // 승부 횟수 카운트
                count++;
            }
        }
        if(count == n-1) answer++; // 승부가 n-1일때 순위 확정
    }
    return answer;
}