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

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

선수의 수는 1명 이상 100명 이하입니다.
경기 결과는 1개 이상 4,500개 이하입니다.
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.

입출력 예

Solution

#include <string>
#include <vector>
#define MAX 101
#define INF 99999999
using namespace std;

int MATRIX[MAX][MAX];


void floydWarshall(int N)
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (MATRIX[i][k] != INF && MATRIX[k][j] != INF)
                {
                    MATRIX[i][j] = min(MATRIX[i][j], MATRIX[i][k] + MATRIX[k][j]);
                }
            }
        }
    }
}


int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) MATRIX[i][j] = INF;
    }
    for(int i = 0; i < results.size() ; i++){
        MATRIX[results[i][0]][results[i][1]] = 1;
    }

    floydWarshall(n);

    for(int i = 1; i <= n; i++){
        int count = 0;
        for(int j = 1; j <= n; j++){
            if(MATRIX[i][j] != INF || MATRIX[j][i] != INF) count++;
        }
        if(count == n - 1) answer++;
    }
    return answer;
}

플로이드 와샬 알고리즘을 통해 각 선수간에 관계를 갱신해주면 되는 문제다.
A가 B를 이긴다고 치자. 해당 관계는 단방향 그래프로 나타낼 수 있다.

위상정렬을 쓰면 안될까? 라는 고민이 들 수도 있다. 그렇지만 이 문제는 너무나 상관관계가 분명하기 때문에 오히려 위상정렬을 썼다가는 답이 없는 상황이 될 수도 있다.

즉 A를 B가 이기고 B가 C를 이겼을 때, A와 C 사이에 상관관계가 있는지를 확인해봐야 한다. 이 상황에서는 플로이드 와샬을 쓰는 게 맞다고 판단했다.

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++) MATRIX[i][j] = INF;
}
for(int i = 0; i < results.size() ; i++){
    MATRIX[results[i][0]][results[i][1]] = 1;
}

우선 모든 노드들을 INF 즉 겁나 큰 값으로 갱신해두고 입력 데이터 대로 인접행렬을 만든다.

void floydWarshall(int N)
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (MATRIX[i][k] != INF && MATRIX[k][j] != INF)
                {
                    MATRIX[i][j] = min(MATRIX[i][j], MATRIX[i][k] + MATRIX[k][j]);
                }
            }
        }
    }
}

그 후 플로이드 와샬을 돌려준다. 단방향 그래프로 이루어진 노드간에 상관관계를 최대한 분석해본다.
플로이드 와샬 매우 중요하니까 복습해보자면 단방향 그래프의 모든 노드들을 찾아보며 혹시 A와 C, C와 B 이런식으로 중간에 상관관계가 있는 놈이 나온다면 저놈을 거쳐서 가는 게 빠를 지, 그냥 가는 게 빠를 지 갱신해주는 알고리즘이다. 원래는 경로 탐색할 때 많이 쓰지만 이렇게 노드 별 상관관계를 분석할 때도 쓰인다.

A가 B를 이겼다고 치자. 근데 A를 C가 이겼다면 B는 C와의 상관관계를 확인해보아야 한다. 모든 노드에 대해 이런 작업을 반복한다.

for(int i = 1; i <= n; i++){
    int count = 0;
    for(int j = 1; j <= n; j++){
        if(MATRIX[i][j] != INF || MATRIX[j][i] != INF) count++;
    }
    if(count == n - 1) answer++;
}

그 후 모든 노드들을 돌면서 한 노드에 얼마나 많은 상관관계가 있는 지 확인한 후 그 상관관계의 갯수가 n-1개 즉 자신을 제외한 모든 선수들 간에 상관관계를 알고있다면 answer에 1을 더한다. 해당 선수는 나머지 선수들과 어떤 상관관계를 가졌는지 알고있으니 순위를 매길 수 있다.

플로이드 와샬이든 다익스트라든 다양한 그래프 알고리즘들이 있지만, 마냥 경로를 찾거나 하는데만 쓰이지는 않는다. 정보를 추상적인 그래프로 처리할 수 있다면 이러한 알고리즘을 문제를 해결하는 데 쓰일 수 있다는 걸 알게 해주는 문제였다.