백준 10597번 순열장난

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

문제풀이

사용한 알고리즘 : Bruteforce( DFS활용 )

(1) 코드 8~43

 주어진 빈칸 없는 순열을 끝까지 순서대로 탐색합니다.
 매 탐색시
    1. 코드 23~29
       해당 숫자로 순열을 만들어 보고 알맞은 순열을 만들 수 있으면 탐색을 끝낸다.
    2. 코드 30~40
       해당 숫자를 십의 자리로 올리고, 다음 수를 일의 자리로 받은 후 탐색을 해본다.
 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	string S;
	int Ssize;
	bool visited[55];
	bool DFS(int curr, vector<int> temp, int maxi) {
	if (temp.size() > 50) return false;
	if (curr == Ssize) {
	int Stemp = temp.size();
	if (Stemp == maxi) {
	for (auto ans : temp)
	cout << ans << ' ';
	cout << '\n';
	return true;
	}
	return false;
	}
	int t = S[curr] - '0';
	if (t > 0) {
	if (!visited[t]) {
	temp.push_back(t);
	visited[t] = true;
	if (DFS(curr + 1, temp, max(t, maxi))) return true;
	temp.pop_back();
	visited[t] = false;
	}
	if (curr < Ssize - 1) {
	t *= 10;
	t += S[curr + 1] - '0';
	if (t <= 50 && !visited[t]) {
	temp.push_back(t);
	visited[t] = true;
	if (DFS(curr + 2, temp, max(t, maxi))) return true;
	temp.pop_back();
	visited[t] = false;
	}
	}
	}
	return false;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> S;
	Ssize = S.length();
	vector<int> v;
	DFS(0, v, 0);
	return 0;
	}

view raw BOJ 10597.cpp hosted with ❤ by GitHub