이번 문제는 BFS를 통해 해결하였다. 자신에게 진 사람을 담는 인접 리스트와 자신에게 이긴 사람을 담는 인접 리스트를 만들고 BFS를 통해 두 인접 리스트를 순회하며 자신에게 진 사람의 수, 이긴 사람의 수를 구하였다. 최선의 등수는 1+자신에게 이긴 사람의 수로 구하였고, 최악의 등수는 n-자신에게서 진 사람의 수를 빼 구하였다.

Code

from collections import deque
n, m, x = map(int, input().split())
win = [[] for _ in range(n+1)]
lose = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    win[a].append(b)
    lose[b].append(a)
def find_rank():
    q = deque()
    q.append(x)
    visited = [False for _ in range(n+1)]
    visited[x] = True
    w_cnt = 0
    l_cnt = 0
    while q:
        cur = q.popleft()
        for nxt in win[cur]:
            if not visited[nxt]:
                w_cnt += 1
                visited[nxt] = True
                q.append(nxt)
    visited = [False for _ in range(n+1)]
    visited[x] = True
    q.append(x)
    while q:
        cur = q.popleft()
        for nxt in lose[cur]:
            if not visited[nxt]:
                l_cnt += 1
                visited[nxt] = True
                q.append(nxt)
    return w_cnt, l_cnt
w_cnt, l_cnt = find_rank()
best = 1+l_cnt
worst = n-w_cnt
print(best, worst)