사용자 도구

사이트 도구


ps:problems:programmers:49191

순위

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호49191
문제명순위
레벨Level 3
분류

그래프

시간복잡도O(V^3)
인풋사이즈V<=100
사용한 언어Python
해결날짜2021/07/02
태그

고득점 Kit - 그래프

풀이

  • 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

토론

댓글을 입력하세요:
I P K N U
 
ps/problems/programmers/49191.txt · 마지막으로 수정됨: 2021/09/07 14:27 저자 teferi