[백준] (34560) 브레인롯 챔피언십 [Python]

링크

https://www.acmicpc.net/problem/34560

문제

골마는 'Italian Brainrot'이라는 밈에 중독되어 버렸습니다. 오늘도 트랄랄레로 트랄랄라와 퉁퉁퉁퉁퉁퉁퉁퉁 사후르를 외치고 다닌다고 합니다. 그러다가 골마는 과연 'Italian Brainrot'에 나오는 캐릭터 중 누가 이길까 궁금해졌습니다.

 

골마는 마침내 'Italian Brainrot' 세계관의 모든 캐릭터들을 모아 그들의 서열을 정리하기 위한 '제1회 브레인롯 챔피언십'을 개최했습니다. 각 캐릭터는 Potenza(힘) P, Agilità(민첩) A, Surrealismo(초현실성) S라는 세 가지 능력치를 가지고 있습니다.

 

두 캐릭터가 맞붙었을 때, 세 능력치에 대해 각 능력치가 같거나 높으면 승 수를 1씩 얻으며 승 수가 더 높은 캐릭터가 승리합니다. 예를 들어, '트랄랄레로'가 '봄바르디로'보다 힘과 민첩이 높지만 초현실성은 같다면, '트랄랄레로'는 3승 0패이고 '봄바르디로'는 1승 2패가 되어 '트랄랄레로'가 승리합니다. 두 캐릭터가 얻은 승 수가 같다면, 아무도 이기지 않습니다.

 

하지만 이 세계는 혼돈 그 자체라, A가 B를 이기고, B가 C를 이기는데, C가 다시 A를 이기는 'Paradoxe Absurdo(부조리한 역설)' 관계가 발생하기도 합니다. 부조리한 역설은 임의의 캐릭터 수열 H (H_1, H_2, ..., H_k)와 모든 정수 i (1 ≤ i < k)에 대해, H_i가 H_{i+1}을 이기고, H_k가 H_1을 이기는 경우로 정의합니다.

 

골마를 도와 이 혼돈의 챔피언십에서 그 누구에게도 패배하지 않는 '궁극의 승리자'를 찾아내 주세요. 그러나 'Paradoxe Absurdo(부조리한 역설)'이 한 번이라도 발생한다면, 궁극의 승리자의 목록 대신 Paradoxe Absurdo를 출력해 주세요.

예제 입력	예제 출력
3 Tralalero 100 80 50 Bombardiro 90 70 60 Spaghetto 80 60 70	Tralalero

코드

from collections import deque

n = int(input())
arr = list()
G = [list() for _ in range(n)]
D = [0] * n

for i in range(n):
    name, p, a, s = input().split()
    arr.append((name, int(p), int(a), int(s)))

for i in range(1, n):
    for j in range(i):
        point_i, point_j = 0, 0
        for k in range(1, 4):
            if arr[i][k] > arr[j][k]:
                point_i += 1
            elif arr[i][k] < arr[j][k]:
                point_j += 1
            else:
                point_i += 1
                point_j += 1
        if point_i > point_j:
            D[j] += 1
            G[i].append(j)
        elif point_i < point_j:
            D[i] += 1
            G[j].append(i)

res = list()
queue = deque()
for i in range(n):
    if D[i] == 0:
        queue.append(i)
        res.append(arr[i][0])

tmp = list()
while queue:
    cur = queue.popleft()
    tmp.append(cur)
    for g in G[cur]:
        D[g] -= 1
        if D[g] == 0:
            queue.append(g)

if len(tmp) != len(arr):
    print("Paradoxe Absurdo")
elif not res:
    print("Paradoxe Absurdo")
else:
    res.sort()
    for r in res:
        print(r)

해설

위상 정렬을 이용해서 푸는 문제로, 최종 출력인 진입 차수가 원래 0인 노드들만 출력하되, 방향 그래프에서 연결된 다음 노드들의 진입 차수를 1씩 줄이면서 사이클이 존재하는지 확인해야 한다.