[백준] 2252 줄 세우기

백준 2252 줄 세우기

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

• 위상 정렬 문제

• 학생들을 키 순서대로 줄을 세운 결과를 출력하기만 하면 된다
  -> 위상 정렬이 불가능한 경우(= 의존성 그래프에 사이클이 존재하는 경우 = 의존성 그래프가 DAG가 아닌 경우)를 고려하지 않아도 된다

DFS를 이용한 풀이

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

int n, m;
vector<vector<int>> adj;
vector<int> seen, order;

//깊이 우선 탐색을 진행하며 dfs종료 순서 기록
void dfs(int here) {
	seen[here] = 1;
	for (int i = 0; i < adj[here].size(); ++i) {
		int there = adj[here][i];

		if (!seen[there])
			dfs(there);
	}
	order.push_back(here);
}

void topologicalSort() {
	//dfsAll
	for (int i = 0; i < n; ++i) {
		if (!seen[i]) dfs(i);
	}
	
	reverse(order.begin(), order.end());

	for (int i = 0; i < order.size(); ++i)
		cout << order[i] +1<< " ";
	
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	adj = vector<vector<int>>(n, vector<int>(0));
	seen = vector<int>(n, 0);
	order.clear();

	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;

		adj[u - 1].push_back(v - 1);
	}

	topologicalSort();
	return 0;
}

Queue를 이용한 풀이

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

int n, m;

//inDegree[i]: 정점i에 들어가는 간선의 수
vector<int> inDegree;
//child[i]: 노드i를 선행 노드로 하는 노드들의 집합
vector<vector<int>> child;

//위상 정렬 함수
void topologySort() {

	vector<int> result(n, 0);
	queue<int> q;

	//진입 차수 0인 정점 큐에 삽입
	for (int i = 0; i < n; ++i)
		if (inDegree[i] == 0) q.push(i);
	
	//정렬이 완전히 수행되기까지 n개의 정점을 방문한다
	for (int i = 0; i < n; ++i) {
		//n개의 정점을 방문하기 전에 큐가 비어버리면 
		//사이클이 발생한 것이다
		if (q.empty()) return;

		//진입 차수가 0인 정점 선택
		int parent = q.front();
		result[i] = parent;

		//선택된 정점과 여기에 부속된 모든 간선들 삭제
		q.pop();
		for (int i = 0; i < child[parent].size(); ++i) {
			int childnode = child[parent][i];
			//새롭게 진입차수가 0이 된 정점을 큐에 삽입
			if (--inDegree[childnode] == 0)
				q.push(childnode);
		}
	}

	//위상 정렬 결과 출력
	for (int i = 0; i < n; ++i)
		cout << result[i] + 1 << " ";

	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	inDegree = vector<int>(n, 0);
	child = vector<vector<int>> (n, vector<int>(0));

	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;

		child[u-1].push_back(v - 1);
		inDegree[v - 1]++;
	}

	topologySort();
	return 0;
}