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

문제

• 링크

코딩테스트 연습 - 순위 | 프로그래머스

힌트

• 어느 노드를 통해서 다른 노드에 다달를 수 있는데 그때 사용하는 것이 플로이드-워셜 알고리즘이다.
• 자신에게 올 수 있는 노드의 수와 자신이 갈 수 있는 노드의 수의 합이 N-1 일 때 확실히 자신의 순위를 알 수 있다.

소스코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> results) {
  int answer{0};

  // 플로이드를 써서 다른 vertex를 거쳐서라도 갈 수 있으면 edge 값 update
  // 나보다 큰 수 + 나보다 작은 수 = N-1 이면, 확실히 알 수 있는 수

  bool** rows = new bool* [n];
  for (int i = 0; i < n; i++) {
    rows[i] = new bool [n];
  }
  for (int i = 0; i < results.size(); i++) {
    int from = results[i][0];
    int to = results[i][1];
    rows[from-1][to-1] = true;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if ((rows[i][k] == true) && (rows[k][j] == true)) rows[i][j] = true;
      }
    }
  }
  for (int k = 0; k < n; k++) {
    int num{0};
    for (int i = 0; i < n; i++) {
      if ((i != k) && ((rows[i][k] == true) || (rows[k][i] == true))) {
        num++;
      }
    }
    if (num == (n-1)) answer++;
  }
  return answer;
}