백준 10597: 순열장난

문제 요약

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

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

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

문제 분류

• 백트래킹

문제 풀이

0번 인덱스부터 1개 혹은 2개의 수를 사용하여 검색해 나가면 된다. 이때 검색한 수가 0이거나, 50보다 크거나, 이미 사용되었다면 false를 리턴하여 이전 방향대로 되돌아가준다. 그렇지 않으면 cnt를 인덱스로, 결과 배열에 넣어준다. 다음에 재귀하여 호출할 때에는 cnt + 1로 다음 인덱스를 지정해주면 된다.

함수 내부에서는 1개를 먼저 탐색해보고, 해당 dfs가 false일 경우 다음에 2개를 탐색하는 것으로 진행한다. 그렇게 진행하다가 마지막에, 즉 탐색 시작 번호와 탐색범위(1~2)의 합이 문자열의 길이보다 길어진다면 지금까지 탐색한 순열이 맞는지 검사하게 되는데, 여기서 순열은 중복없이 1~N, 즉 지금까지 세어온 cnt + 1의 값과 N의 값이 같아야 하므로 1부터 cnt + 1까지 탐색하지 않은 수가 있다면 해당 결과는 false가 된다.

시간초과의 원인은 다양하지만, 순열에서 중복을 허용하고 있지는 않은지 확인해보자.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool used[51];
int res[50];
string s;

bool valid(int cnt) {
	for (int i = 1; i <= cnt + 1; i++)
		if (used[i] == 0) return false;
	return true;
}

bool dfs(int idx, int range, int cnt) {
	int val;
	if (range == 1) val = s[idx] - '0';
	else val = (s[idx] - '0') * 10 + s[idx + 1] - '0';
	if (val == 0 || val > 50 || used[val]) return false;
	used[val] = true;
	res[cnt] = val;
	if (idx + range >= s.length()) {
		if (valid(cnt)) {
			for (int i = 0; i < cnt + 1; i++)
				printf("%d ", res[i]);
			return true;
		}
		used[val] = false;
		return false;
	}
	if (dfs(idx + range, 1, cnt + 1)) return true;
	else if (dfs(idx + range, 2, cnt + 1)) return true;
	used[val] = false;
	return false;
}

int main()
{
	cin >> s;
	
	if (dfs(0, 1, 0)) return 0;
	else dfs(0, 2, 0);

	return 0;
}