BOJ 2252 - 줄 세우기

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

 

접근방법

이번 문제는 위상정렬 문제라는 것을 사전에 알고 풀었다.

왜 위상정렬로 풀어야할지 생각해봤다.

 

총 N명의 학생들 중 임의의 두 학생 A와 B의 키만 비교하였다.

그리고 이렇게 잰 키를 통해 줄을 세운다.

이는 A와 B를 정점으로 생각할 때, A와 B는 단방향 간선을 가진 그래프가 된다.

 

이를 통해, 위상정렬하여 각 정점들의 순서를 정할 수 있기 때문에 위상정렬을 사용하였다.

 

위상정렬을 다시 짧게 설명하면

 

각 정점들의 간선은 무조건 단방향이어야 한다. (순환 발생 X)

진입차수(나한테 들어오는 간선의 수)가 0인 애들을 찾아서 줄 세우는 것이 위상정렬이다.

 

1. 진입차수가 0인 정점을 큐에 넣는다.

2. 큐가 빌때까지 pop을 하여, 해당 정점의 간선들 중 해당 정점에서 나가는 반대 정점의 진입차수를 -1 한다.

3. 만약 반대 정점의 진입차수가 0이 되면 큐에 넣는다.

4. 큐에서 나온 순서가 위상정렬된 것이다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>

#define MAX 32001

using namespace std;

int n, m;
int a, b;

// 단방향 그래프
vector<int> v[32001];
int indegree[32001];
queue<int> q;
vector<int> res;

void topologySort() {
	// 초기에 진입차수 0인 정점들을 넣어줌
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int popped = q.front();
		q.pop();

		cout << popped << ' ';

		// popped -> opposite 인거의 opposite의 진입 차수 --
		// 만약 opposite의 진입차수가 0이면 q에 push
		for (auto opposite : v[popped]) {
			indegree[opposite]--;
			if (indegree[opposite] == 0)
				q.push(opposite);
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		// a -> b
		v[a].push_back(b);
		indegree[b]++;
	}

	topologySort();
}

학부때 공부한 내용이라 쉽게 해결할 수 있었다.