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

1. 문제

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

2252번: 줄 세우기

 

2. 알고리즘 분류

• 그래프 이론
• 위상 정렬

 

3. 소스 코드

Key Point)
1. 그래프를 이용하여 학생 순서를 정리한다.
2. '위상 정렬'을 사용하여 그래프 순서대로 값을 정렬한다.

 

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

using namespace std;

int N, M;
int visited[MAX_N];
int inDegree[MAX_N];
vector<int> graph[MAX_N];
vector<int> path;

// 위상 정렬 알고리즘
void topological_sort()
{
	// 모든 노드 탐색 
	for (int i = 1; i <= N; i++)
	{
		// 진입차수가 0이 아니거나, 이미 방문한 노드이면 건너뛰기
		if (inDegree[i] || visited[i]) continue;

		queue<int> q;

		visited[i] = 1;	// 방문 체크
		q.push(i);	// Queue에 추가

		// Queue 빌때까지 탐색
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();
			path.push_back(cur);	// 경로 추가

			// 해당 노드의 간선 탐색
			for (int j = 0; j < graph[cur].size(); j++)
			{
				int next = graph[cur][j];

				// 이미 방문했거나, 차감한 진입차수가 0이 아니면 건너뛰기
				if (visited[next] || --inDegree[next] != 0) continue;

				visited[next] = 1;	// 방문 체크
				q.push(next);	// Queue에 추가
			}
		}
	}
}

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// N : 학생 수, M : 키를 비교한 횟수
	cin >> N >> M;

	// 키를 비교한 결과 입력
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;

		graph[a].push_back(b); // 그래프 추가
		inDegree[b]++; // 진입차수 추가
	}

	// 위상 정렬 알고리즘
	topological_sort();	

	// 정렬된 결과 출력
	for (auto item : path)
		cout << item << " ";

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) 위상 정렬

1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘
2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행
3. 시간 복잡도 = O(V + E)

https://uigwonblog.tistory.com/50

[알고리즘] 위상 정렬(Topological Sorting)