(C++) - 프로그래머스(고득점 kit - 그래프) : 순위

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

플로이드 와샬 문제였습니다.

 

풀이방법

 1. 누가 누구를 이겼는지에 대한 정보를 담을 2차원 배열 gameInfo라는 변수를 선언합니다. i선수가 j선수를 이겼다면 gameInfo[i][j] = 1이 됩니다.

 

 2. 플로이드 와샬을 수행해서 누락된 승부 정보를 알아냅니다.

 만약 i가 k를 이겼고 k가 j를 이겼다면 삼단논법에 의해 i는 j를 이긴것이 됩니다.

 

 3. i가 j를 이겼거나 i가 j에게 패배했다면 그 개수를 세줍니다. 예를들어 2번 선수의 순위가 도출되려면 1,3,4,5번 선수와의 승부정보가 있어야합니다. 즉 승패여부와 상관없이 정보만 있다면 count해줍니다. 그 결과가 n-1(자기 자신 제외)이라면 순위를 도출할 수 있으므로 answer를 1 더해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    int gameInfo[101][101];
    memset(gameInfo,0,sizeof(gameInfo));

    for(auto &r : results)
        gameInfo[r[0]][r[1]] = 1;

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(gameInfo[i][k] && gameInfo[k][j])
                    gameInfo[i][j] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++)
            if(gameInfo[i][j] || gameInfo[j][i])
                cnt++;
        if(cnt == n-1)
            answer++;
    }

    return answer;
}