[파이썬] [그래프] Pro 순위

문제

https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3 

코딩테스트 연습 - 순위

 

코드

def solution(n, results):
    answer = 0
    array=[[None]*(n+1) for _ in range(n+1)]

    for i,j in results:
        array[i][j]=True
        array[j][i]=False

    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                if array[j][i]==None:
                    continue
                if array[j][i]==array[i][k]:
                    array[j][k]=array[j][i]
                    array[k][j]=not(array[j][i])
    for i in range(1,n+1):
        if None in array[i][1:i]:
            continue
        if None in array[i][i+1:]:
            continue
        answer+=1
    return answer

생각 정리

a가 b를 이겼다면 b는 항상 a 아래이고, b가 c를 이겼다면 c도 항상 b 아래이다

결국 c는 항상 a아래 이므로

a->b, b->c이면 a->c 인 것이므로 플로이드와샬로 접근이 가능하다.

 

a와 b 관계에서 a가 c를 이기고 c가 b를 이기는 관계가 있으면

a가 b를 이긴것으로 체크하고 (b,a), (c,a), (b,c)는 모두 진것으로 체크하면 된다.