[Programmers] 순위 - [그래프, 플로이드-워셜]

[Programmers] 순위 - [그래프, 플로이드-워셜]

문제 링크

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

문제 요약

$n$명의 권투 선수가 1:1 경기를 치르고, 일부 경기 결과(results)가 주어집니다. A 선수가 B 선수를 이기고, B 선수가 C 선수를 이기면 A 선수는 C 선수를 이긴 것으로 간주합니다(실력의 추이성). 이때, 정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제입니다.

접근 방법

• 자료구조: 2차원 배열 (인접 행렬 graph[n][n])
• 알고리즘: 플로이드-워셜 (Floyd-Warshall)
• 핵심 아이디어:
  • 승패의 연결: i가 k를 이기고 k가 j를 이겼다면, i는 j를 이긴 것입니다. 이 성질을 이용해 모든 선수 간의 승패 관계를 파악합니다.
  • 순위 확정 조건: 한 선수 i가 본인을 제외한 n-1명의 다른 모든 선수와의 승패 관계(이겼거나 졌거나)가 명확하다면, 그 선수의 순위는 확정됩니다.

풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    // graph[i][j] = true : i가 j를 이김
    // 인덱스 편의를 위해 n+1 크기로 생성
    vector<vector<bool>> graph(n + 1, vector<bool>(n + 1, false));

    // 1. 주어진 경기 결과 반영
    for (auto& edge : results) {
        int winner = edge[0];
        int loser = edge[1];
        graph[winner][loser] = true;
    }

    // 2. 플로이드-워셜 알고리즘 수행
    // k: 거쳐가는 선수, i: 이긴 선수, j: 진 선수
    // i가 k를 이기고, k가 j를 이기면 -> i는 j를 이김
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][k] && graph[k][j]) {
                    graph[i][j] = true;
                }
            }
        }
    }

    // 3. 순위 확정 가능한 선수 세기
    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            // 내가 이겼거나(graph[i][j]), 내가 졌거나(graph[j][i])
            // 승패 관계가 확실하면 카운트
            if (graph[i][j] || graph[j][i]) {
                count++;
            }
        }
        // 나를 제외한 모든 선수(n-1명)와 승패 관계가 있으면 순위 확정 가능
        if (count == n - 1) {
            answer++;
        }
    }

    return answer;
}

시간/공간 복잡도

• 시간 복잡도: $O(n^3)$
  • 3중 중첩 반복문(플로이드-워셜)을 사용하므로 n^3에 비례합니다. n <= 100이므로 약 100만 번의 연산으로 충분히 빠릅니다.
• 공간 복잡도: $O(n^2)$
  • n * n 크기의 2차원 배열(인접 행렬)을 사용합니다.

실행 결과

• 메모리: 약 4MB 내외 (입력 크기에 따라 상이)
• 시간: 0.01ms ~ 1.00ms 내외 (매우 빠름)

핵심 포인트

1. 플로이드-워셜 응용: 최단 거리를 구하는 알고리즘이지만, 여기서는 단순 연결성(승패 관계의 전파)을 확인하는 용도로 사용합니다.
2. 순위의 정의: '정확한 순위'를 안다는 것은 '나보다 강한 사람'과 '나보다 약한 사람'의 합이 전체 인원수에서 나를 뺀 값(n-1)과 같다는 의미입니다.

예제 확인

• 예제 1:
  • 입력: n=5, results=[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
  • 과정:
    • 4 > 3, 3 > 2 -> 4 > 2 (이미 존재)
    • 4 > 2, 2 > 5 -> 4 > 5
    • 1 > 2, 2 > 5 -> 1 > 5
    • 3 > 2, 2 > 5 -> 3 > 5
    • 최종적으로 2번 선수는 [1, 3, 4]에게 지고 [5]를 이김 (총 4명 관계 확인 -> 순위 확정)
    • 5번 선수는 [2]에게 지는데, 2가 [1, 3, 4]에게 졌으므로 5번도 [1, 3, 4]에게 짐 (총 4명 관계 확인 -> 순위 확정)
  • 결과: 2