문제 푼 날짜 : 2021-08-16

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49191

접근 및 풀이

문제를 보자마자 Floyd-Warshall 알고리즘을 이용하는 문제라는 것을 알았다.
(유사문제 : https://www.acmicpc.net/problem/2458)
문제는 아래와 같은 알고리즘을 통해 코드를 구현하였다.

1. 주어진 조건으로 가중치 방향 그래프를 만들어준다.
   1-1. 주어진 조건에서 [A, B]는 A 선수가 B 선수를 이겼다는 의미라고 했으니, 이를 그래프에서는 A에서 B로 향하는 것으로 나타내어 arr[A][B] = 1 로 할당한다.
2. 만들어진 그래프에 Floyd-Warshall 알고리즘을 적용하여 각 선수에서 모든 다른 선수로의 거리를 구해준다.
3. 구해준 배열에서 arr[A][B](A->B를 의미) 또는 arr[B][A](B->A를 의미)가 INF 값이 아니라면 A와 B사이에 이동가능한 간선이 존재한다는 뜻이고, 이는 누가 이길지 결정할 수 있다는 의미이다.
4. 그래서 각 선수마다 다른 선수사이의 간선이 모두 존재한다면 순위를 매길 수 있는 선수인 것이다. 이를 만족하는 선수의 수를 세어주면 된다.

코드

#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 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제였다.