[Python] BOJ 백준 21937 작업

문제

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

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

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

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

풀이

단순히 재귀함수 구현으로 풀 수 있는 문제였다. 깊이 탐색을 이용해서 각 작업의 선행 작업들을 처리하게 하고,

스택에서 빠져 나오면서 답을 도출할 수 있었다. 

from collections import deque
import sys

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n, m = MIIS()
todo = [[] * (n + 1) for _ in range(n + 1)]
tree = [0] * (n + 1)
visited = [False] * (n + 1)
sys.setrecursionlimit(10 ** 6)

for _ in range(m):
    a, b = MIIS()
    todo[b].append(a)

x = int(si())


def dfs(x):
    if not todo[x]:
        visited[x] = True
        return 0
    for node in todo[x]:
        if not visited[node]:
            tree[x] += dfs(node) + 1
            visited[node] = True
    return tree[x]


print(dfs(x))