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

프로그래머스: 순위

문제 링크

플로이드 와샬로 모든 정점에서 모든 정점의 관계를 파악해서 풀 수 있는 문제였다. 구체적인 순위가 필요한 것이 아니라 "정확하게 순위를 매길 수 있는 선수의 수"를 구하는 것이 목적이므로, 플로이드 와샬을 이용해서 모든 정점(선수)에서 모든 정점(선수)까지의 경로를 찾는다. 경로가 존재한다면 승패가 가려진 상황이므로, 한 정점에서 다른 모든 정점까지의 경로가 존재하는 경우라면 순위를 정확하게 매길 수 있다. 처음에 배열을 int로 선언했을 때는 계속 오답이라고 나왔는데, 이유를 모르겠다. 어차피 0이냐, 아니냐만 따지면 되기 때문에 문제될 것이 없다고 생각했는데 왜일까?

풀이

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

bool arr[101][101];

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

    for(auto r : results) {
        arr[r[0]][r[1]] = true;
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(arr[i][k] && arr[k][j]) {
                    arr[i][j] = true;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++) {
            if(arr[i][j] || arr[j][i]) cnt++;
        }
        if(cnt == n - 1) answer++;
    }

    return answer;
}