백준(C++) 2252번 줄 세우기 풀이

C++로 구현한 2252번 줄 세우기 문제 풀이입니다.

 

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

2252번: 줄 세우기

---

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001

using namespace std;

int n, inDegree[MAX], result[MAX];
vector<int> a[MAX];

void topologySort() {
	queue<int> q;
	for(int i=1; i<=n; i++) {
		if(inDegree[i] == 0) {
			q.push(i);
		}
	}
	for(int i=1; i<=n; i++) {
		int x = q.front();
		q.pop();
		result[i] = x;
		for(int j=0; j<a[x].size(); j++) {
			int y = a[x][j];
			if(--inDegree[y] == 0) {
				q.push(y);
			}
		}
	}
	for(int i=1; i<=n; i++) {
		printf("%d ", result[i]);
	}
}

int main() {
	int m;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		a[x].push_back(y);
		inDegree[y]++;
	}
	topologySort();
}

 

문제에서 N 값의 범위가 32,000까지이기 때문에 MAX의 값을 32,001로 지정해준다.

 

메인코드에 정점의 개수와 키를 비교하는 횟수를 입력받고 반복문 내에서는 입력된 정점 x와 y의 값을 연결해준 뒤

 

연결된 정점의 진입 차수를 1 증가시켜준다. 위상 정렬 알고리즘 수행에 해당하는 topologySort() 함수에서는

 

큐를 사용하도록 하며, 진입 차수가 0인 노드를 큐에 삽입한다. 두번째 반복문에서 정점의 개수만큼 반복하도록 하고

 

큐에 가장 먼저 들어온 원소를 꺼낸 뒤 result[i] 에 담는다. 그리고 해당 정점의 간선 수만큼 반복하여 새롭게 진입차수가

 

0이 된 정점을 큐에 삽입한다. 위와 같은 과정을 반복적으로 수행한다.

 

 

  * 위상 정렬 알고리즘 수행 과정 및 정보는 아래의 글에서 확인하시면 됩니다.

https://unie2.tistory.com/44

위상 정렬(Topology Sort)