[백준] 21937번 작업

문제 링크: https://www.acmicpc.net/problem/21937

아이디어

1. 작업들 간의 연결관계를 단방향 그래프로 저장한다.
   chart[work_num] = [work_num번 작업을 하기 위해 선행되어야 하는 작업들]
2. 오늘 반드시 끝내야하는 작업에서 시작하여 그래프 탐색을 수행한다. 선행 작업이 없는 작업까지 도달한다면 탐색을 종료한다.

ex)
오늘 반드시 끝내야하는 작업이 5번 작업이라면, 5 $\rightarrow$ 4 $\rightarrow$ 2 순으로 탐색한다.

코드

import sys
from collections import deque
input = sys.stdin.readline


class FlowChart():
    def __init__(self, num_of_work: int = 0, chart=None) -> None:
        self.num_of_work = num_of_work
        self.chart = chart

    def minimum_workload(self, target: int = 0) -> int:

        if self.chart == None:
            raise Exception("There is no chart")
        if target == 0:
            raise Exception("The target is wrong")

        visited = [False]*(work_chart.num_of_work+1)
        visited[target] = True
        queue = deque([target])
        cnt = 0

        while queue:
            node = queue.popleft()
            for next_node in self.chart[node]:
                if visited[next_node] == False:
                    queue.append(next_node)
                    visited[next_node] = True
                    cnt += 1

        return cnt


def init_data():
    num_of_work, work_order = map(int, input().split())
    work_info = [[] for _ in range(num_of_work+1)]
    for _ in range(work_order):
        pre, post = map(int, input().split())
        work_info[post].append(pre)
    target = int(input())

    return flowchart(num_of_work, work_info), target


if __name__ == "__main__":
    work_chart, target = init_data()
    print(work_chart.minimum_workload(target))

결과

deque가 아니고 stack을 이용하였을 때는 다음과 같이 메모리와 시간이 증가하는 것을 확인할 수 있다. (https://docs.python.org/3/tutorial/datastructures.html)