[백준 / 21937] 작업 - 파이썬(Python)

문제

민상이는 자신이 해야할 작업 N개를 아래와 같이 작업 순서도로 그려보았다.

위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.

작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.

민상이는 오늘 반드시 끝낼 작업 X가 있다. 민상이가 작업 X 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!

입력

민상이가 작업할 개수 N와 작업 순서 정보의 개수 M이 공백으로 구분되어 주어진다.

두 번째줄부터 M+1 줄까지 작업 Ai와 작업 Bi가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작업 Bi를 하기 위해서 바로 이전에 작업 Ai를 먼저 해야한다는 의미이다. 중복된 정보는 주어지지 않는다.

마지막 줄에는 민상이가 오늘 반드시 끝내야하는 작업 X가 주어진다.

출력

민상이가 작업 X를 하기 위해 먼저 해야하는 일의 개수를 출력한다.

제한

•  1 ≤ N ≤ 100,000
•  0 ≤ M ≤ min(N×(N−1)/2, 200000)
•  1 ≤ Ai, Bi ≤ N
•  1≤ X ≤N

21937번: 작업

 

문제 풀이

주어진 노드에서부터 부모로 가면서 부모의 수를 세어주면 된다.

from collections import deque
input = __import__('sys').stdin.readline
MIIS = lambda: map(int, input().split())

N,M = MIIS()
cnt = 0
work = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(M):
	a, b = MIIS()
	work[b].append(a)

start = int(input())
que = deque()
que.append(start)
visited[start] = True

while que:
	x = que.popleft()
	for i in work[x]:
		if not visited[i]:
			visited[i] = True
			cnt += 1
			que.append(i)

print(cnt)