[Python/파이썬] 백준 17616번: 등수 찾기

문제

 

풀이

등수를 찾을 노드 위로 몇 개의 노드가 있는지,

아래로 몇 개의 노드가 있는지 구하면 된다.

 

코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n, m, x = map(int, input().split())

up = [[] for _ in range(n + 1)]
down = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    down[a].append(b) # a 아래에 b
    up[b].append(a) # b 위에 a

visited = [False] * (n + 1)

def dfs(x, graph, cnt):
    visited[x] = True
    cnt[0] += 1
    for next in graph[x]:
        if not visited[next]:
            dfs(next, graph, cnt)

upNode = [-1]
downNode = [-1]
dfs(x, up, upNode)
dfs(x, down, downNode)

print(1 + upNode[0], end = " ")
print(n - downNode[0])

 

마무리

방법을 떠올리는데 시간이 꽤 걸렸고, 코드 작성은 쉬웠다.