[백준 알고리즘] 2252번 줄세우기 문제풀이 c++

1766번 문제집 풀이가 비슷하다

https://hoji25.tistory.com/27

[백준 알고리즘] 1766번 문제집 문제풀이 c++

 

order 벡터에는 자기보다 키가 큰 학생의 번호를 저장한다.

ex) 3번학생보다 4번, 5번 학생이 키가 크다면 order[3]벡터에는 4,5가 저장되어있다.

cnt배열에는 자기보다 키가 작은 학생의 수가 저장되어있다.

 

자기보다 키가 작은 학생이 0명이면 바로 줄을 설 수 있으므로

queue에 push한다.

queue가 empty일때까지 while문을 돌면서

x번(queue의 top) 학생의 order[x]를 확인하여

x번 학생보다 키가 큰 학생들의 cnt값을 줄여주고

cnt가 0이면 queue에 push한다.

 

#include <iostream>
#include <queue>

using namespace std;

int cnt[32001];
vector<vector<int>> order(32001);

int main(){
	int n, m;

	cin >> n >> m;

	int x1, x2;
	for(int i=0; i<m; i++){
		cin >> x1 >> x2;
		cnt[x2]++;
		order[x1].push_back(x2);
	}
	
	queue<int> q;

	for(int i=1; i<=n; i++){
		if(cnt[i] == 0){
			q.push(i);
			cnt[i] = -1;
		}
	}

	while(!q.empty()){
		int x = q.front();
		cout << x << " ";
		q.pop();
		for(int i=0; i<order[x].size(); i++){
			if(--cnt[order[x][i]] == 0){
				q.push(order[x][i]);
				cnt[order[x][i]] = -1;
			}
		}
	}

	return 0;
}