문제 링크

풀이 과정

전체 코드


from collections import defaultdict

def solution(n, results):
    '''
    1) A 선수에게 진 B 선수는, A 선수로부터 승리한 선수한테도 패배한다.
    2) A 선수로부터 승리한 B 선수는, A 선수에게 패배한 선수로부터 승리한다.
    '''
    answer = 0
    win_graph = defaultdict(set)   # 각 선수 별 승리를 거둔 선수의 집합  ex) 2: {5}
    lose_graph = defaultdict(set)  # 각 선수 별 패배를 당한 선수의 집합  ex) 2: {1, 3, 4}

    for winner, loser in results:        
        win_graph[winner].add(loser) 
        lose_graph[loser].add(winner)

    for i in range(1, n+1):
        # case 1) A 선수에게 진 B 선수는, A 선수로부터 승리한 선수한테도 패배한다.
        for loser in win_graph[i]:
            lose_graph[loser].update(lose_graph[i])
        # case 2) A 선수로부터 승리한 B 선수는, A 선수에게 패배한 선수로부터 승리한다.
        for winner in lose_graph[i]:
            win_graph[winner].update(win_graph[i])

    # 이긴 선수 합과 진 선수의 합이 n-1(자기 자신은 제외하므로)이면, 순위가 고정됩니다.
    for i in range(1, n+1):
        if len(win_graph[i]) + len(lose_graph[i]) == n-1:   
            answer += 1

    return answer