문제 : 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;
}
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ] 4485 : Obstacle Course - travelbeeee (0) | 2020.04.10 |
|---|---|
| [BOJ] 16953 : A -> B - travelbeeee (0) | 2020.04.10 |
| [BOJ] 10868 : 최솟값 - travelbeeee (0) | 2020.04.09 |
| [BOJ] 6549 : Largest Rectangle in a Histogram - travelbeeee (0) | 2020.04.09 |
| [BOJ] 17178 : 줄서기 - travelbeeee (0) | 2020.04.07 |