위상 정렬(Topological sorting)
위상 정렬이란?(What is Topological Sorting?) 위상 정렬의 뜻을 검색해보면 "DAG에 대한 위상 정렬은 정점 u에서 정점 v로 가는 방향이 있는 간선이 있을 때 모든 정점 u가 모든 정점 v 앞에 오도록 정점을 정렬하는 선형 정렬"이라고 나온다. 이 말이 쉽게 와닿지 않을 수 있다. 하지만 게임의 테크트리를 생각하면 어떤 말인지 쉽게 알 수 있다. 우리가 게임을 하다보면 어떤 기술을 열거나 건물을 건설할 때 요구 조건이 있는 것을 한번쯤은 봤을 것이다. 그리고 요구 조건을 충족할 때만 기술을 열거나 건물을 건설할 수 있다. 이때 각 건물과 기술들이 정점이 되는 것이고 요구 조건과 관련된 건물과 기술의 관계가 간선이라고 생각하면 된다. 그런데 위상 정렬 앞에 DAG란 조건이 붙어..
