[백준 21937번] 파이썬 - 작업

백준 21937 - 작엽

시간 제한 1초, 메모리 제한 512MB

# 조건

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

• 위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다.
• 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.
• 작업 순서를 정할때 위배되는 작업 순서는 없다.
  • 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.
• 민상이는 오늘 반드시 끝낼 작업 X가 있다.
• 민상이가 작업 X 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!

입력

• 민상이가 작업할 개수 N와 작업 순서 정보의 개수 M이 공백으로 구분되어 주어진다.
• 두 번째줄부터 M + 1 줄까지 작업 A_i와 작업 B_i가 공백으로 구분되어 주어진다.
  • 이때 두 값의 의미는 작업 B_i를 하기 위해서 바로 이전에 작업 A_i를 먼저 해야한다는 의미이다.
  • 중복된 정보는 주어지지 않는다.
• 마지막 줄에는 민상이가 오늘 반드시 끝내야하는 작업 X가 주어진다.

출력

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

# 접근 방법

• 민상이가 끝내야하는 작업 X를 하기 위한 일의 개수를 구해야하므로, 작업 X에서부터 그래프 탐색을 해주면 된다.
• 이를 위해서 입력받는 작업간의 관계를 반대로 기록해준다.
• BFS를 이용하여 X에서부터 해야하는 작업을 넣어주며 cnt + 1씩하여 기록해주고 출력하면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(now):  
    q = deque([(now)])  
    visited = [False] * (N+1)  
    visited[now] = True  
    cnt = 0  
    while q:  
        val = q.popleft()  
        for i in graph[val]:  
            if visited[i] == False:  
                q.append(i)  
                cnt += 1  
                visited[i] = True  

    print(cnt)  


N, M = map(int, input().split())  
graph = [[] for _ in range(N+1)]  
for _ in range(M):  
    a, b = map(int, input().split())  
    graph[b].append(a)  

X = int(input())  
bfs(X)