알고리즘/위상정렬(Topological Sort) (1) 썸네일형 리스트형 위상정렬 대표적인 2문제 비교 처음문제를 풀당시 기존의 위상정렬에서 정점들의 선행순서를 위반하지만 않는다면 어떤 순서로 정렬해도 상관이 없었지만 14567, 선수과목 (Prerequisite) 문제에서는 각과목의 누적학기를 표시해 주어야 했다. 이걸 어떻게 누적시키지? 생각하며 재귀를 이용해야 하나? 라는 생각도 잠시 했었다. 하지만 심플하게 반복문을 돌면서 기존에 deque에 저장되어있던 학기정보인 cnt를 popleft하고 append하는 과정에서 자연스럽게 누적되는 학기수를 다룰수 있었다. 두 코드의 비교! 1. 전형적인 (위상)정렬 코드에서는 그래프를 표현하기위해 인접행렬을 사용하였지만 선수과목 문제에서는 사전과 리스트를 사용해 그래프를 표현하였다! 2. (위상)정렬 코드에서는 진입차수가 0인 정점을 저장하기 위해 vacant.. 이전 1 다음