[BOJ] 2529 : 부등호 - travelbeeee

문제 : https://www.acmicpc.net/problem/2529

---

위상정렬 백트레킹 부르트포스

1) 백트레킹, 부르트포스를 이용한 풀이

 K가 최대 9이므로, 모든 숫자 조합을 만들어서 다 검사하는 백트레킹 + 부르트포스 방법을 생각했다. 복잡도는 O((K+1) * (K+1)!) 으로 K가 최대여도 시간 초과 문제에 걸리지 않는다.

● 백트레킹을 이용해 K + 1 개의 숫자 조합을 만든다. 이때, 백트레킹을 가장 작은 수부터 숫자 조합을 만들게 구현한다.

● 숫자 조합이 만들어지면 부등호에 맞는 숫자인지 checkNumber 함수를 이용해 체크한다.

● 우리는 백트레킹을 가장 작은 수부터 만들게 구현했으므로, 첫 번째로 부등호에 맞는 숫자가 가장 작은 값이 되므로 가장 작은 값으로 저장하고, 그 뒤로는 값이 점점 더 커지므로 큰 값으로 계속 저장해준다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int k;
string ans1, ans2;
bool checkS, chk[10];
char op[10];

bool checkNumber(vector<char> v) {
	for (int i = 0; i < k; i++){
		if (op[i] == '<') {
			if (v[i] >= v[i + 1]) {
				return false;
			}
		}
		else if (op[i] == '>') {
			if (v[i] <= v[i + 1]) {
				return false;
			}
		}
	}
	return true;
}

void BT(vector<char> v) {
	if (v.size() == k + 1) {
		bool flag = checkNumber(v);
		if (!flag)
			return;
		string temp = {};
		for (int i = 0; i < v.size(); i++)
			temp += v[i];
		if (checkS == false){ // 첫 가장 작은 값 저장.
			checkS = true;
			ans1 = temp;
		}
		ans2 = temp;
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (chk[i] == false) {
			chk[i] = true;
			v.push_back(char(i + '0'));
			BT(v);
			v.pop_back();
			chk[i] = false;
		}
	}
}

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

	cin >> k;
	for (int i = 0; i < k; i++)
		cin >> op[i];

	vector<char> v;
	BT(v);

	cout << ans2 << '\n' << ans1;
	return 0;
}

2) 위상정렬을 이용한 풀이

 1번 풀이로 시간 초과를 직면하지는 않았지만, 다른 분들 채점 현황을 보니 더 좋은 알고리즘이 있는 것 같아 고민하다가 위상정렬을 이용한 알고리즘을 발견했다.

● 가장 작은 값을 찾을 때는, 작은 숫자부터 앞쪽에 배치해야하므로 A < B 상태가 오면 A -> B 로 간선을 주고 inDegree가 0인 노드 중 가장 번호가 작은(앞쪽인) 노드부터 남은 숫자 중 가장 작은 값을 줍니다.

● 가장 큰 값을 찾을 때는, 큰 숫자부터 앞쪽에 배치해야하므로 A < B 면 A <- B 로 간선을 주고, 마찬가지로 inDegree가 0인 노드 중 가장 번호가 작은(앞쪽인) 노드부터 남은 숫자 중 가장 큰 값을 줍니다.

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;

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

	int k, inDegree[10] = {}, revInDegree[10] = {};
	vector<int> map[10], revMap[10];
	char ans1[11] = {}, ans2[11] = {};
	char temp;
	cin >> k;
	for (int i = 0; i < k; i++){
		cin >> temp;
		if (temp == '<') { // i 에서 i + 1로 
			map[i].push_back(i + 1);
			inDegree[i + 1]++;
			revMap[i + 1].push_back(i);
			revInDegree[i]++;

		}
		else {
			map[i + 1].push_back(i);
			inDegree[i]++;
			revMap[i].push_back(i + 1);
			revInDegree[i + 1]++;
		}
	}
	// 가장 작은 값 부터 찾자.
	priority_queue<int, vector<int>, greater<int>> pq;
	bool check[10] = {}; // 사용한 값 저장.
	for (int i = 0; i <= k; i++)
		if (inDegree[i] == 0)
			pq.push(i);
	while (!pq.empty()) {
		int curNode = pq.top(); pq.pop();
		for (int i = 0; i < 10; i++)
			if (check[i] == false) {
				ans1[curNode] = char(i + '0');
				check[i] = true;
				break;
			}
		for (int i = 0; i < map[curNode].size(); i++) {
			inDegree[map[curNode][i]]--;
			if (inDegree[map[curNode][i]] == 0)
				pq.push(map[curNode][i]);
		}
	}
	// 가장 큰 값을 찾자.
	memset(check, false, sizeof(check));
	for (int i = 0; i <= k; i++)
		if (revInDegree[i] == 0)
			pq.push(i);
	while (!pq.empty()) {
		int curNode2 = pq.top(); pq.pop();
		for (int i = 9; i >= 0; i--){
			if (check[i] == false) {
				ans2[curNode2] = char(i + '0');
				check[i] = true;
				break;
			}
		}
		for (int i = 0; i < revMap[curNode2].size(); i++) {
			revInDegree[revMap[curNode2][i]]--;
			if (revInDegree[revMap[curNode2][i]] == 0)
				pq.push(revMap[curNode2][i]);
		}
	}
	cout << ans2 << '\n' << ans1;
	return 0;
}

---