1.풀이 (1) 주어진 선후관계만으로 q와 graph를 구성한다 (2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다. ​ * 두가지풀이 - 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음 - 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음 ​ 2. 소스코드 (1) 소스코드1 (python3 시간초과) import heapq N,M=map(int,input().split()) fromNode={} toNode={} for i in range(1,N+1): fromNode[i]=[] toNode..

1. 풀이 (1) 입력값 아래의 두 리스트로 그래프를 관리한다 parent[i] : i 노드로 들어오는 노드들을 저장한 리스트 garph[i]: i노드에서 향하는 노드들을 저장한 리스트 이후 정석대로 간선을 삭제한 후, parent[i]가 비어있는 노드들을 차례대로 q에 넣어서 탐색한다. ​ (2) 위상정렬 이때 각 노드의 최소완료시간을 구해야 하기 때문에 ans[toNode]=max(ans[nowNode]+time[toNode],ans[toNode])를 수행해 주어야 한다. ans[i] : i건물까지 만드는데 드는 최소시간 time[i] : i건물을 만드는데 드는 시간 q에서 뽑힌 노드 i의 ans[i]는 최소시간으로 보장된상태이다. 그리고 ans[nowNode]+time[toNode]가 ans[toN..

1. 위상정렬? 2. 방법 어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다. 기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다. 3. 소스코드 #include #include #include #include using namespace std; // 부무노드 개수 저장 int parent[32001]; // togo[i]에는 i가 향하는 정점들을 저장 vector togo[32001]; queue q; int main() { int N, M; cin >> N >> ..