프로그래머스 - 순위 (c++)

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

프로그래머스

보통 그래프 문제가 주어지면 양방향 그래프로 주어지는 경우가 많은데, 이 문제는 단방향 그래프이다.

A가 B를 이겼다는 경우가 주어지면 'A -> B' 이렇게 노드를 저장한다.

또, 이 문제에는 '플로이드-와샬' 이라는 최단거리 알고리즘이 사용된다. (다익스트라도 최단 거리 알고리즘!)

boolean값을 저장하는 2차원 배열을 만드는데, win[a][b]에 저장되어 있는 값은 a가 b를 이겼으면 true / 졌으면 false값을 저장한다.

플로이드-와샬 알고리즘은 A, B, C 세 사람의 승/패 여부가 궁금할 때 사용된다. 예를 들어, A가 B를 이겼고 B가 C를 이겼을때 A와 C의 승/패 여부를 알기 위해서는 win[A][B]와 win[B][C]가 모두 true 값을 가지는지 확인할때 사용된다.

또한, 한 선수의 순위를 알기 위해서는 N명의 선수가 있다고 할 때, 승/패 횟수가 N-1번이 기록되어야 본인의 순위를 알 수 있다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

bool win[101][101];
int solution(int n, vector<vector<int>> results) {
  int answer = 0;
  for (auto a : results) {
    win[a[0]][a[1]] = true;
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (win[i][k] && win[k][j])
          win[i][j] = true;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int j = 1; j <= n; j++) {
      if (i == j)
        continue;
      if (win[i][j] || win[j][i])
        cnt++;
    }
    if (cnt == n - 1)
      answer++;
  }
  return answer;
}