[GeeksForGeeks] Topological Sort using Kahn's Algorithm

이론 정리한지 1년이 넘어서 풀어보는 예제

 

🔒 문제

 

위상 정렬 순서에 맞는 answer vector를 리턴하라.

 

🔑 풀이

class Solution{
	public:
	vector<int> topoSort(int V, vector<int> adj[]) {
        int * indegree = new int[V]{0};
        std::vector<int> answer;

        // initialize indegree array
        for (int i = 0; i < V; i++) {
            for (const auto& adjacentVertex : adj[i]) {
                indegree[adjacentVertex]++;
            }
        }
    
        std::queue<int> queue;
        // indegree 0 찾고 넣기
        for (int i = 0; i < V; i++) {
            if(indegree[i] == 0) queue.push(i);
        }
    
        // 비어있을 때 까지 모두 찾아 죽여버려!
        while (!queue.empty()) {
            const int targetVertex = queue.front();
            queue.pop();
            answer.emplace_back(targetVertex);
            
            // update indegree
            for (const auto& adjacentVertex : adj[targetVertex]) {
                indegree[adjacentVertex]--;
                // 새로 0된애 있으면 찾고 넣기
                if (indegree[adjacentVertex] == 0) queue.push(adjacentVertex);
            }
        }
        
        return answer;
	}
};

원큐에 풀이 성공했다. 기분 좋구먼

 

 

이론 정리 글

Topological Sort(위상 정렬)

결과