[프로그래머스/C++] 순위

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

풀이

입출력 예시

 

풀이

이 문제는 최단 경로를 구하는 알고리즘 중 하나인 플로이드-워셜 알고리즘을 구현할 수 있다면 쉽게 풀 수 있는 문제였다.

 

results 배열을 참고해서 그래프를 구성해준다. graph[i][j] = true 라는 뜻은, i가 j를 이겼다는 뜻이다. graph[j][k] = true 라면 j가 k를 이겼으므로, i 도 k를 이겼을 것이다. 이 부분을 플로이드-워셜 알고리즘으로 구현해준다.

 

순위를 매길 수 있는 경우는, 만약 4명의 선수가 있었고, 1번 선수가 2번을 상대로 이기고 3번을 상대로 졌다고 하자. 1번 선수가 4번 선수를 상대로 이겼는지 졌는지를 모르므로 순위를 매길 수 없다. 즉, n명이 있을 때 n - 1만큼의 결과를 모르면 순위를 확정할 수 없다.

 

위 코드들을 조합해서 순위를 매길 수 있는 선수의 수를 구하면 되는 문제였다.

#include <string>
#include <vector>

using namespace std;

vector<vector<bool>> result;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    result.resize(n + 1, vector<bool>(n + 1, false));
    
    for (const auto& re : results) {
        result[re[0]][re[1]] = true;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (result[j][i] && result[i][k]) {
                    result[j][k] = true;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (result[i][j] || result[j][i]) {
                count++;
            }
        }
        if (count == n - 1) {
            answer++;
        }
    }
    
    return answer;
}