[백준 2252번 C/C++] 줄 세우기

 

[백준 2252번 C/C++] 줄 세우기

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

---

 

해결 전략

 

위상 정렬 Topological Sort Algorithm

 

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m; 					// n은 학생의 수, m은 키를 비교한 횟수
vector<vector<int>> graph;  // 각 학생의 키를 비교한 결과를 나타내는 그래프
vector<int> inDegree; 		// 각 노드의 진입 차수를 저장하는 배열
vector<int> result; 		// 위상 정렬을 통해 정렬된 순서를 저장하는 배열

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m; 
	graph.resize(n+1); 
	inDegree.resize(n+1); 

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b; 
		graph[a].push_back(b); 	// a번 학생이 b번 학생보다 작다는 관계를 그래프에 추가
		inDegree[b]++; 			// b번 학생의 진입차수를 1 증가
	}

	queue<int> Q; // 진입차수가 0인 노드를 저장할 큐
	
	for (int i = 1; i <= n; i++) { // 진입차수가 0인 학생을 큐에 모두 넣는다.
		if (inDegree[i] == 0) {
			Q.push(i);
		}
	}

	// 위상 정렬
	while (!Q.empty())
	{
		int idx = Q.front(); 	// 큐에서 학생 번호를 가져옴
		Q.pop(); 				// 해당 학생을 큐에서 제거
		result.push_back(idx);  // 결과 배열에 해당 학생 번호를 추가

		for (int i = 0; i < graph[idx].size(); i++) { // idx번 학생보다 큰 학생들에 대해 처리
			int next = graph[idx][i];

			inDegree[next]--; // 다음 학생의 진입차수를 1 감소 시킴

			if (inDegree[next] == 0) { 	// 만약 진입차수가 0이 되었다면
				Q.push(next); 			// 큐에 다음 학생을 추가
			}
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}

 

 

---