[백준] 2252번 줄 세우기

문제: 2252번: 줄 세우기

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int n, m; // n: 학생 수, m: 키를 비교한 횟수
	cin >> n >> m;
	vector<vector<int>> linkedList(n + 1); // 학생 번호는 1부터 시작하니까 n+1 로 해주기.. 0번 인덱스 안 쓸 것


	vector<int> answer; // 정답 저장할 곳
	stack<int> noInDegree; // 진입 디그리가 없는 노드들 저장하는 곳
	vector<int> inDegree(n+1); // 각 정점의 진입 디그리 저장하는 곳(얘도 마찬가지로 0번 인덱스 안 쓸 것)


	// m 개의 줄에는 키를 비교한 두 학생의 번호 A, B 가 주어짐
	// -> A 가 B 앞에 서야 한다
	// 즉, A 노드가 B 노드를 가리킨다는 말과 같음
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		linkedList[a].push_back(b); // a 노드가 b 노드를 가리키고 있음
		inDegree[b] += 1; // 진입 디그리 +1 해주기
	}

	for (int i = 1; i < n + 1; i++) {
		// 진입 간선이 없는 애들을 noInDegree 에 넣어놓고 시작하기
		if (inDegree[i] == 0)
			noInDegree.push(i); 
	}

	while (!noInDegree.empty()) {
		int node = noInDegree.top();
		noInDegree.pop();

		answer.push_back(node); // 진입 간선이 없는 노드를 answer 에 저장

		// 이제 이 노드랑 연결되어 있는 노드들의 진입 디그리를 -1 해줘야함
		for (int i = 0; i < linkedList[node].size(); i++) {
			int v = linkedList[node][i]; // 이웃 노드 번호 

			inDegree[v]--; // 이웃 노드의 진입 디그리 -1

			// 만약 이웃한 노드의 진입 디그리가 0이 되면 noInDegree 에 넣기
			if (inDegree[v] == 0)
				noInDegree.push(v);
		}
	}

	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << " ";
	cout << "\n";


	return 0;
}

 

아주 기초적인 위상 정렬 개념 문제였다. 기본 위상 정렬 방식을 그대로 적용하면 쉽게 해결할 수 있다.

 

일단 입력으로 n: 학생수, m: 키 비교 횟수 가 주어지고 다음 m 개의 줄에 키를 비교한 두 학생의 번호 a, b 가 주어진다. 이는 a 가 b 앞에 서야 한다는 것을 의미한다고 문제 조건으로 주어졌다.

 

a 가 b 앞에 서야 한다는 것은 다시 생각해보면 a 와 b 를 정점이라고 했을 때 정점 a 가 정점 b 를 가리키는 것이 되겠다. 즉, 문제에서는 특정 정점 사이의 연결 관계를 입력으로 주고 있다.

 

정점 사이의 연결관계를 표현하기 위해서는 링크드리스트를 쓰면 된다. 나는 링크드리스트의 크기를 n+1 로 설정했는데 문제 입력으로 주어지는 학생의 번호가 1부터 N 번까지라고 했기 때문에 인덱스 계산을 편하게 하기 위함이었다.

 

그렇다면 이제 위상정렬을 본격적으로 구현해야 하는데 이를 어떻게 할 수 있을까? 핵심은 어떤 정점이 있을 때 그 정점으로 들어오는 진입 간선이 없다면 스택에 넣어주고, 나중에 스택에서 값을 빼서 answer 에 저장하고, 그 정점과 연결된 정점의 진입 간선 수를 -1 해준다. 이때 만약 연결된 정점의 진입 간선 수가 0이 되면 이제 이를 다시 스택에 넣어주면 되는 것이다.

 

스택이 비어있지 않을 때까지 위 과정을 반복해주면 된다.

 

오늘은 꽤나 쉬워서 기분이 좋았다. 관련 문제 몇 개 더 풀어보면 좋을 것 같다.