백준 2252번 줄 세우기

문제링크

문제 해설

접근법

학생의 관계가 1 대 1이 아닌 1대 N의 관계가 가능하므로 그래프 문제이다.

또한, 순서와 방향이 있는 그래프 + 정렬해야 하므로 위상 정렬을 사용하였다.

풀이

위상정렬은 큐를 이용하여 풀이할 수 있다.

이 문제에서는 본인 앞에 서 있어야 할 학생의 수를 배열로 저장하여 풀이하였다.

1. 입력을 받으면서 본인 앞에 서 있어야 할 학생의 수를 배열로 저장한다. 이를 배열 p라 하자.
2. 입력을 받으면서 본인 뒤에 서 있어야 할 학생의 번호를 배열로 저장한다. 이를 배열 arr라 하자.
3. 배열 p를 확인하면서 p[i]가 0인 번호 i를 큐에 넣어준다.
4. 큐에서 하나씩 꺼내어 출력한다. 또한 꺼낸 값 i의 arr[i]에 속해 있는 학생 x의 p값을 감소시킨다. => 노드간의 연결을 끊는다
5. 4번에서 만약 p[x]가 0이 되었다면 큐에 x를 넣어준다.
6. 큐가 빌 때까지 4,5번을 반복한다.

소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int p[32001];
vector<int> arr[32001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	// 1 + 2
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		p[b]++;
		arr[a].push_back(b);
	}
	queue<int> q;
	// 3.
	for (int i = 1; i <= n; i++) {
		if (p[i] == 0) {
			q.push(i);
		}
			
	}
    // 6.
	while (!q.empty()) {
		int from = q.front();
		q.pop();
		cout << from << " ";
		for (int i = 0; i < arr[from].size(); i++) {
			int to = arr[from][i];
			p[to]--;	// 4.
			// 5.
			if (p[to] == 0) {
				q.push(to);
			}
		}
	}

	return 0;
}