[プログラマー]ランキング

11245 ワード
supin2 プログラマ cpp level3 テキストリンク
回答日:2021-08-16

質問する


質問リンク:https://programmers.co.kr/learn/courses/30/lessons/49191

アクセスと解析


問題を見るとFloyd-Warshallアルゴリズムを利用した問題であることがわかる.
(類似問題:https://www.acmicpc.net/problem/2458)
問題は以下のアルゴリズムによってコードを実現した.
  • で与えられた条件に基づいて重み付け方向図を作成する.
    1-1. 与えられた条件で[A,B]はA選手がB選手に勝ったことを示し,グラフではAからBを示しarr[A][B]=1に割り当てられる.
  • で生成されたグラフにFloyd-Warshallアルゴリズムを適用し,各選手から他の選手までの距離を求める.
  • で得られた配列でarr[A][B](A−>Bを意味する)またはarr[B][A](B−>Aを意味する)がINF値でない場合、AとBの間に移動可能な幹線が存在することを示し、これは誰が勝つかを決定できることを意味する.
    • したがって、
  • は、選手ごとに異なる選手間の幹線が存在する場合、ランキングできる選手である.これに満足する選手の数だけ数えておけばいい.

    • コード#コード#

    #include <string>
#include <vector>

using namespace std;

#define INF 987654321

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    int arr[101][101];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                arr[i][j] = 0;
            } else {
                arr[i][j] = INF;
            }
        }
    }
    for (auto r : results) {
        arr[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 (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                continue;
            } else {
                if (arr[i][j] != INF || arr[j][i] != INF) {
                    cnt++;
                }
            }
        }
        if (cnt == n - 1) {
            answer++;
        }
    }
    return answer;
}

    結果



    フィードバック


    Floyd-Warshallアルゴリズムを知っていれば、簡単に解決できる問題です.
    C. Stable Groups Div.2
    TIL 210721