[python] 백준 17616 등수 찾기

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

17616번: 등수 찾기

 

문제 해결

• DFS로 내 앞에 최소 몇명이 있는지 구하고, 내 뒤에 최소 몇명이 있는지 쉽게 구할 수 있다.
• 최고 등수는 한 명도 앞에 없을 때 1등이라 하고 앞에 있는 사람의 명수가 늘어날 때마다 1씩 더해준다.
• 최저 등수는 꼴등이라 가정하고 뒤에 한 명씩 단서가 생길 때마다 1씩 빼주며 등수를 구한다.
• 함께 구하는 방법은 생각하지 못했다.
• DFS를 두 번 사용해서 pypy3로는 통과했는데 python3는 만점을 받지 못했다.

 

CODE

import sys
input = sys.stdin.readline


def up(num):
    if len(upstream[num]) ==0:
        return
    
    for i in range(len(upstream[num])):
        if visited_up[upstream[num][i]] ==0:
            visited_up[upstream[num][i]] = 1
            ans[0] += 1
            up(upstream[num][i])

def down(num):
    if len(downstream[num])==0:
        return
    
    for i in range(len(downstream[num])):
        if visited_down[downstream[num][i]] == 0:
            visited_down[downstream[num][i]] = 1
            ans[1] -=1
            down(downstream[num][i])

if __name__=='__main__':
    n, m, x = map(int ,input().split())
    upstream =  [[] for _ in range(n+1)]
    downstream = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b= map(int ,input().split())
        upstream[b].append(a)
        downstream[a].append(b)
    visited_up = [0 for _ in range(n+1)]
    ans = [1,n] # 최고등수, 최저등수
    visited_up[x] = 1
    up(x)
    visited_down = [0 for _ in range(n+1)]
    visited_down[x] = 1
    down(x)
    print(*ans)