Level 3. 순위

Level 3. 순위

 

 

 

플로이드-워셜(Floyd-Warshall) 알고리즘

그래프 탐색 알고리즘
- 노드의 개수가 100개 미만으로 적은 것이 특징이다.
  시간 복잡도가 3중 for문을 사용하는 O(n³)이기 때문이다.
- 특정 점들이 아닌 모든 점들 사이의 최단 거리를 구한다.
- 음수 가중치가 있어도 사용할 수 있지만, 음수 사이클은 존재해선 안 된다.

1. 가중치가 정해지지 않은 간선들은 ∞로 초기화한다.
    ∞를 무작정 INT_MAX로 설정하면, 더할 때 음수가 돼버리므로 주의해야 한다.
2. 자기 자신의 비용은 0으로 초기화한다.
3. K (임의의 중간 점) → S (시작점) → E (끝점) 순으로 3중 for문을 구성하여 최단 거리를 갱신한다.

 

[프로그래머스] 순위(Floyd-Warshall Algorithm)

 

이 문제에서는 n개의 정점으로 구성된 그래프를 만들어, (자신에게 도달할 수 있는 점들의 개수) + (자신이 도달할 수 있는 점들의 개수)가 (n - 1)이 되면 된다.

• 무승부나 이기고 또 진 경우는 없으므로, (내가 이긴 사람의 수)와 (나를 이긴 사람의 수)가 (나를 제외한 n - 1)이면 순위를 확정할 수 있다.
• 비용이 아닌 승패만 확인하면 되므로 비용은 1로 설정해도 된다.
• 편의상 자기 자신은 0으로 초기화하지 않았다.

 

#include <iostream>
#include <vector>
#include <algorithm>

#define TBD 100

using namespace std;

int solution(int n, vector<vector<int>> results)
{
    int answer = 0;
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, TBD));

    for (vector<int>& r : results)
        graph[r[0]][r[1]] = 1;

    for (int k = 1; k <= n; ++k)
        for (int s = 1; s <= n; ++s)
            for (int e = 1; e <= n; ++e)
                graph[s][e] = min(graph[s][e], graph[s][k] + graph[k][e]);

    for (int i = 1; i <= n; ++i)
    {
        int nDtrm = 0;

        for (int j = 1; j <= n; ++j)
            nDtrm += (graph[i][j] != TBD) + (graph[j][i] != TBD);

        answer += (nDtrm == (n - 1));
    }

    return answer;
}