백준 2252번 줄 세우기

< 백준 2252번 줄 세우기 - 마포 코딩박 >

사용한 알고리즘: 위상정렬


학생들의 부분적인 순서가 입력으로 주어졌을 때, 이를 만족하는 총 학생들의 배열을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~8, 15~22)
 'arr[i] : i 학생 뒤에 와야하는 학생들' , 'indegree[x] : x학생 앞에 서야하는 학생 수' 라고 설정하였습니다.
 각 입력을 받으며 arr 와 indegree를 최신화 해주었습니다.

(2) (코드 23~27)
 indegree가 0인, 즉 자신의 앞에 와야하는 학생이 없는 학생들을 골라 queue를 만들어 넣었습니다. 이 학생들은 맨 처음에 올 수 있는 학생들입니다.

(3) (코드 28~37)
 queue에 넣은 학생들을 하나씩 꺼내며, 그 순서가 곧 답이므로 답을 만듭니다.
 꺼낸 학생의 arr 를 둘러보며, 그 학생의 자식들의 indegree-- 를 해줍니다. 이때 indegree=0 이 되는 자식학생이 있으면 queue에 다시 넣어줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 위상정렬
	int N, M;
	// arr[i] : i 학생 뒤에 와야 하는 학생들 (i학생의 자식)
	vector<int> arr[32003];
	// indegree[i]: i 학생 앞에 와야 하는 학생 수
	int indegree[32003];
	vector<int> ans;
	queue<int> QQ;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; ++i){
	int next, pre;
	cin >> pre >> next;
	// 뒤 학생의 indgree++
	indegree[next]+=1;
	// 앞 학생의 자식 추가
	arr[pre].push_back(next);
	}
	for (int i = 1; i <= N; ++i){
	// 자신의 앞에 올 학생이 없는 학생 선별
	if(indegree[i]==0)
	QQ.push(i);
	}
	while(!QQ.empty()){
	int now = QQ.front();
	QQ.pop();
	ans.push_back(now);
	for(auto iter : arr[now]){
	indegree[iter]--;
	// now학생의 자식들 중 now학생이 빠지면서 indegree=0 이 되는 학생 선별
	if(indegree[iter]==0) QQ.push(iter);
	}
	}
	for (int i = 0; i < N; ++i)
	cout << ans[i] << ' ';
	cout << '\n';
	return 0;
	}

view raw BOJ 2252.cpp hosted with ❤ by GitHub