이론 정리한지 1년이 넘어서 풀어보는 예제 🔒 문제 위상 정렬 순서에 맞는 answer vector를 리턴하라. 🔑 풀이 class Solution{ public: vector topoSort(int V, vector adj[]) { int * indegree = new int[V]{0}; std::vector answer; // initialize indegree array for (int i = 0; i < V; i++) { for (const auto& adjacentVertex : adj[i]) { indegree[adjacentVertex]++; } } std::queue queue; // indegree 0 찾고 넣기 for (int i = 0; i < V; i++) { if(indegree[..

1. 개념 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환..