# topological sorting

ohhj1999

🔒 예제 🔧 풀이 🔑 답안 💡 개념

smsh0722

Topological Sorting은 여러 가지 일들에 순서가 있을 때, 그 순서를 거스르지 않도록 일을 나열하는 것을 말한다. 각 일들을 nodes로 보면 일종의 Directed Graph로 볼 수 있다. 이때, Cycle이 있다면 순서를 거스르지 않는 것이 불가능

smsh0722

시간 제한: 1초메모리 제한: 256MB이러한 상황이 있을 때, 빨간색으로 체크한 부분을 넘어뜨려야 한다. Topological Order 순으로 넘어뜨리면 된다.Topological Sort를 한다.Topological order를 하나씩 pop하면서, 넘어지지 않은

smsh0722

시간 제한: 2초메모리 제한: 512MBNaive 하게 DFS로 모든 경우의 수를 조사하면 만나는 시간을 구하는 데만 O( V\*(V+E) )이다. 이는, 시작 지점에서 도시 u로 가는 시간을 새로 갱신하면, u와 인접한 도시들도 다시 갱신해 주어야 하기 때문에 발생하

smsh0722

시간 제한: 2초메모리 제한: 128MB문제 간의 정해진 순서를 거스르지 않고 정렬해야 한다는 점에서 Topological Sorting 문제이다. 그런데, 문제를 풀 때마다, 앞으로 풀 수 있는 문제의 pool이 달라지는데, 그때마다 가장 쉬운 문제를 풀어야 한다.

smsh0722

시간 제한: 2초메모리 제한: 128MBA가 나온 이후에 B가 다음으로 나와야 한다. 이는 node A에서 node B로 가는 edge로 볼 수 있다. 또한, a->b->c->a 형태는 나올 수 없기 때문에, Cycle이 존재하지 않는다. 따라서, 일종의 Directe

boorook

분류: Topological Sorting (위상정렬)

boorook

분류: Topological Sorting (위상정렬)

jong_p

topological sorting 발견.