순위

• BOJ의 Cow Contest과 동일한 문제. 원 출처는 USACO이다.
• 어떤 선수를 기준으로 {그 선수보다 순위가 낮은 선수의 수} + {그 선수보다 순위가 높은 선수의 수}가 {전체 선수의 수 - 1} 이라면, 그 선수는 순위를 정확하게 매길 수 있다.
• 어떤 선수보다 순위가 낮은 선수들을 찾는 것은, 각 선수가 노드를 이루고, 이긴선수→진선수 로 엣지들이 구성된 그래프를 만들어서, 그 선수에 해당하는 노드에서 출발해서 도달할수 있는 노드들을 찾으면 된다. 순위가 높은 선수들을 찾는 것은 역방향으로 엣지들을 구성해서 똑같이 찾으면 된다. BFS나 DFS를 사용하면 O(V+E)에 찾을수 있다. 모든 선수들에 대해서 이 작업을 해주어야 하므로 O(V*(V+E)) 가 된다.
• 모든 노드들에 대해서, 그 노드를 출발지로 하는 BFS를 돌리는 대신, 플로이드 알고리즘을 이용해도 같은 결과를 얻을수 있다. 시간복잡도가 O(V^3)이지만 코드가 짧아진다. 이 문제에서는 원래 플로이드가 구해주는 각 노드들까지의 최단 거리는 필요 없고, 각 노드들까지의 경로가 있는지 없는지만을 계산하면 되기 때문에 아이디어를 조금 수정해서 적용했다.
  • 코드를 얼핏 보면 플로이드 알고리즘이라는 느낌이 잘 안들텐데.. 자세히 살펴보면 결국 그 방법이다.

"""Solution code for "Programmers 49191. 순위".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/49191
- Solution link: http://www.teferi.net/ps/problems/programmers/49191
"""


def solution(n, results):
    higher_rankers = [set() for _ in range(n)]
    lower_rankers = [set() for _ in range(n)]
    for a, b in results:
        higher_rankers[a - 1].add(b - 1)
        lower_rankers[b - 1].add(a - 1)

    for i in range(n):
        for higher_ranker in higher_rankers[i]:
            lower_rankers[higher_ranker].update(lower_rankers[i])
        for lower_ranker in lower_rankers[i]:
            higher_rankers[lower_ranker].update(higher_rankers[i])            
            
    answer = sum(1 for i in range(n)
                 if len(higher_rankers[i]) + len(lower_rankers[i]) == n - 1)
    return answer