# topological sorting
[BOJ] 1766 문제집
https://www.acmicpc.net/problem/1766아이디어위상정렬 문제임을 캐치각 문제 당 선행 문제 수를 numOfParents\[]에 저장해둔다.numOfParents\[x] == 0인 문제 x를 우선순위 큐에 넣고, 낮은 번호의 문제부터 뽑
[백준] 1948번: 임계경로 with Python
BOJ 1948Topological Sorting월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.이
[BOJ] 2056 작업
https://www.acmicpc.net/problem/2056아이디어위상 정렬 알고리즘 공부하고 시작numOfParents\[]: 각 작업의 선행 작업 수 저장children\[]: 나를 선행 작업으로 필요로 하는 작업 저장endTime\[]: 해당 작업이
Topological Sorting
Topological Sorting은 여러 가지 일들에 순서가 있을 때, 그 순서를 거스르지 않도록 일을 나열하는 것을 말한다. 각 일들을 nodes로 보면 일종의 Directed Graph로 볼 수 있다. 이때, Cycle이 있다면 순서를 거스르지 않는 것이 불가능
4196. 도미노
시간 제한: 1초메모리 제한: 256MB이러한 상황이 있을 때, 빨간색으로 체크한 부분을 넘어뜨려야 한다. Topological Order 순으로 넘어뜨리면 된다.Topological Sort를 한다.Topological order를 하나씩 pop하면서, 넘어지지 않은
1948. 임계 경로
시간 제한: 2초메모리 제한: 512MBNaive 하게 DFS로 모든 경우의 수를 조사하면 만나는 시간을 구하는 데만 O( V\*(V+E) )이다. 이는, 시작 지점에서 도시 u로 가는 시간을 새로 갱신하면, u와 인접한 도시들도 다시 갱신해 주어야 하기 때문에 발생하
1766. 문제집
시간 제한: 2초메모리 제한: 128MB문제 간의 정해진 순서를 거스르지 않고 정렬해야 한다는 점에서 Topological Sorting 문제이다. 그런데, 문제를 풀 때마다, 앞으로 풀 수 있는 문제의 pool이 달라지는데, 그때마다 가장 쉬운 문제를 풀어야 한다.
2252. 줄 세우기
시간 제한: 2초메모리 제한: 128MBA가 나온 이후에 B가 다음으로 나와야 한다. 이는 node A에서 node B로 가는 edge로 볼 수 있다. 또한, a->b->c->a 형태는 나올 수 없기 때문에, Cycle이 존재하지 않는다. 따라서, 일종의 Directe
