프로그래머스: 순위

알고리즘 문제 해결 과정을 기록합니다

September 29, 2025 · 2 min read

문제 개요 #

Source: 프로그래머스 링크
Difficulty: Level 3
Key Concept: 그래프 이론

접근 방법 #

각 선수들의 순위를 결정시키기 위한다는 개념을 어떻게 결졍해야 하는지 많이 고민했던 문제입니다. 선수들의 승패는 Edge를 통해 결정되므로 모든 노드 간 엣지가 연결되어 있으면 순위가 결정되었다고 볼 수 있습니다.

시행착오 #

처음 승패에 따른 엣지를 어떻게 설정해주어야 하는지가 고민되었습니다. 처음 생각했던 방법은 이긴 상대에게만 Edge를 이어주고 weight를 1로 설정시켰습니다. 해당 방법은 승자만 기록되고 패자의 경우 어떠한 기록도 남지 않아 순위를 결정시키는데 적합하지 않았습니다. 따라서 패자도 Edge를 연결시키고 구분되는 wieght값을 넣어주어야 했습니다.

해결 방법 #

#include <bits/stdc++.h>

using std::vector;

int dist[150][150];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
                continue;
            }
            dist[i][j] = INT_MAX;  // No Edge
        }
    }

    for (const auto& game : results) {
        int winner = game.front();
        int looser = game.back();
        dist[winner][looser] = 1;
        dist[looser][winner] = -1;
    }

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

    for (int i = 1; i <= n; i++) {
        if (std::find(std::begin(dist[i]), std::end(dist[i]), INT_MAX) ==
            std::end(dist[i])) {
            answer++;
        }
    }
    return answer;
}

알고리즘 설명 #

패자의 경우 weight를 -1로 하여 승자와 패자를 이어주는 Edge를 생성시켰습니다. 이후 간접적으로 승리한 경우 예를 들어 1번 노드가 2번 노드를 이기고, 2번 노드가 3번 노드를 이겼다면 1번 노드가 3번 노드를 이긴 것으로 간주됩니다. 따라서 dist[1][3] = 1로 설정시킵니다. 이와 같이 패자의 경우도 똑같이 간접적으로 패자로 간주된다면 dist[i][j] = -1로 설정하여 순위를 결정시킬 수 있도록 Edge를 만들어주었습니다.

마지막으로 해당 노드가 INT_MAX를 가지고 있지 않다면 즉, 모든 노드에 대해 연결되어 있다면 순위가 결정된 것이므로 answer를 증가시키고 그렇지 않다면 증가시키지 않도록 하였습니다. 이 떄 std::end(dist[i])는 n보다 큰 값들까지 탐색하게 되나, 모두 값이 0으로 할당된 전역 변수이므로 로직의 문제는 없습니다.

성능 분석 #

Time Complexity: $O(V^3)$

핵심 정리 #

순위를 결정한다는 개념은 모든 노드와 엣지로 연결되어 weight값을 볼 수 있는 상태임을 알아내는 것이 핵심이었습니다. 이를 확인하기 위해서는 모든 노드 간 서로의 거리를 알 수 있어야 합니다. 따라서 이는 플로이드 워셜 알고리즘을 이용하여 풀 수 있습니다.¹

참고자료 #

플로이드 워셜 알고리즘 ↩︎