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

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

2252번: 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

---

대표적인 위상정렬 문제이다. 키를 순서대로 세운다는 말은 방향이 있다는 말로 Directed Graph를 이용하면 된다.

adjacent list (vector<int> a)를 활용하여 입력 정보를 저장한다. 이때 inDegree 배열은 진입 차수로 내 앞에 특정 인물 몇 명이 와야 하는지를 저장하는 배열이다. 입력을 모두 받았다면 이제 위상 정렬을 할 단계이다. 우선 진입 차수들을 확인하여 진입 차수가 0 인 원소들을 큐에 push 한다. 그다음 반복문 1번당 1명의 순서를 정함으로써 반복문을 총 n번 돌아 n명의 순서를 정하도록 한다. i가 n에 도달하지 못하고 큐가 비어있다면 그것은 cycle이 생긴 것이기 때문에 위상 정렬을 할 수 없는 입력정보라고 판단할 수 있다. 반복문마다 큐의 원소를 pop 한다. 이때 이 원소는 i번째 순서로 선택된 것이기 때문에 위에서 설명한 진입 차수에 자신보다 앞에 와야 할 원소 1개가 선택된 것이다. 그러므로 선택된 원소와 인접한 원소들의 진입 차수를 1 감소시킨다. 감소시킨 값이 0일 경우 이제 선택받을 준비가 된 것이므로 queue에 push 하여 다음 반복문에서 선택되길 기다린다.

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

using namespace std;

int n,m, inDegree[32001] = { 0 };
vector<int> a[32001];

void topologySort() {
	int result[100001];
	queue<int> q;

	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) 
			q.push(i);
	}
	for (int i = 1; i <= n; i++) {
		if (q.empty()) {
			cout << "ERROR";
			return;
		}
		int x = q.front();
		q.pop();
		result[i] = x;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (--inDegree[y] == 0)
				q.push(y);
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << result[i] << ' ';
	}
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		a[t1].push_back(t2);
		inDegree[t2]++;
	}
	topologySort();
	return 0;
}

---

많이 들어보기만 했던 위상정렬 문제였다. 4달 전에 푼 기록이 있는 문제였는데 그때는 그래프 문제를 잘 풀지 못했을뿐더러 알고리즘 분류를 보지 않고 풀었기 때문에 다수의 '틀렸습니다'가 기록에 남아있었다. 한 학기 동안 그래프 이론에 대해 공부하고 구글링을 하여 위상 정렬을 검색해보니 전형적인 위상 정렬 문제로 풀이 방법만 알면 정말 쉽게 풀 수 있는 문제였다. 이와 같이 큰 분류의 알고리즘 (Divide & Conquer , DP, Graph) 내에서도 세부적인 풀이를 알면 정말 쉽게 풀 수 있지만 생각해내기는 어려운 문제들이 많은 것 같다. 알고리즘 문제를 다양하게 접해보고 다양한 문제에 적합한 다양한 풀이법을 숙지해놓는 것이 좋을 것 같다!

 

추가로 어제 포스팅을 못하였다. 일요일을 제외하고 매일 포스팅을 하고 싶었지만 어제 선형대수학 기말고사가 끝나자 마자 삼성 알고리즘 특강의 사전 문제 풀이를하였는데 몇 시간을 투자하여 1문제를 푸나 싶었지만 테스트 케이스 10개 중 4개만 통과하고 나머지는 시간 초과가 떴다. 나보다 먼저 시작한 친구들도 다른 문제를 풀었는데 테스트 케이스의 반 정도만 되고 나머지는 시간 초과가 떴다고 하였다. 사실 백준 문제들을 풀면 배열 같은 것을 선언할 때 그냥 100001, 32001과 같이 통 크게 선언해도 알고리즘만 맞으면 시간 초과나 메모리 초과가 거의 안나는 편이라 이렇게 선언했는데 최적화를 해야 하려고 하니 막막했다. 또, 백준 문제를 풀 때 구현에는 손이 잘 안 가고 문제가 간단하고 풀이가 딱 핵심 알고리즘을 이용하는 문제도 주로 풀었는데 이렇게 구현할 것이 많은 문제는 오랜만이라 조금 버겁긴 하였다. 그래도 푸는 도중에 코드의 결과도 못 보고 끝이 날거라 생각했는데 그래도 구현을 다 하자마자 테스트 케이스 4개는 통과한 것은 되게 뿌듯하였다. 인덱스 범위나 이런 것들로 꽤나 고생할 줄 알았는데 나름 구현을 잘했더라.