[G5] 백준 1469번 숌 사이 수열 C++ 백트래킹, 정렬

리뷰

 

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

처음 풀어보는 완전 탐색 문제 유형이었다.

 

 

전역 변수

• n : 수열의 크기를 저장할 변수
• path : 숌 사이 수열을 저장할 벡터
• ap : 입력 받은 원소를 저장할 벡터
• flag : 숌 사이 수열이 완성 되었는지 여부를 저장할 변수
• cnt : 각 수의 등장 횟수를 저장할 배열

 

함수

1. bt

void bt(int level) {
	if (flag) return;
	if (level == n * 2) {
		for (int i : path) cout << i << " ";
		flag = true;
		return;
	}

	for (int i : ap) {
		if (cnt[i] > 1) continue;
		else if (cnt[i] == 0) {
			++cnt[i];
			path.push_back(i);
			bt(level + 1);
			path.pop_back();
			--cnt[i];
		}
		else {
			int len = path.size();
			if (len - i - 1 >= 0 && path[len - i - 1] == i) {
				++cnt[i];
				path.push_back(i);
				bt(level + 1);
				path.pop_back();
				--cnt[i];
			}
		}
	}
}

 

백트래킹을 통해 숌 사이 수열을 만드는 모든 경우를 탐색하고, 찾은 최초의 수열을 출력하는 함수

 

 

문제풀이

1. n값을 입력 받고, n개의 수열 원소를 입력 받아 ap벡터를 초기화한다.
2. sort함수를 통해 ap벡터를 오름차순으로 정렬한다.
3. bt함수에 매개변수 0을 호출한다, 함수 내부에선 변수 level에 이를 파싱해 재귀 레벨을 저장한다.
4. 첫 번째 기저 조건으로 flag가 true일 경우 이미 숌 사이 배열이 완성된 상태이므로 리턴한다.
5. 두 번째 기저 조건으로 level이 n*2에 도달한 경우 path의 요소를 출력, flag를 true로 저장 후 리턴한다.
6. ap를 순회하며 cnt[i]가 2이상일 경우 continue처리한다.
7. cnt[i]가 0일 경우 cnt를 증가시키고, path에 i를 추가, 재귀를 수행하고, 재귀를 빠져나올 시 원상 복구 처리한다.
8. cnt[i]가 1일 경우 path의 뒤에서 i번째 요소가 i일 경우 동일한 재귀와 원상 복귀 과정을 수행한다.
9. bt함수가 종료된 후 flag가 false인 상태라면 -1을 출력한다.

 

트러블 슈팅

1. 예제는 다 맞았지만 ap벡터를 오름차순으로 정렬하지 않아 1%에서 WA를 받았다.
2. sort함수를 통해 ap벡터 원소를 오름차순으로 정렬 후 제출하니 AC를 받았다.

 

참고 사항

1. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다.
2. 숌 사이 수열이 여러 개일 경우 사전 순으로 가장 빠른 것을 출력한다. 따라서 정렬이 필요하다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<int> path;
vector<int> ap;
bool flag;
int cnt[17];

void bt(int level) {
	if (flag) return;
	if (level == n * 2) {
		for (int i : path) cout << i << " ";
		flag = true;
		return;
	}

	for (int i : ap) {
		if (cnt[i] > 1) continue;
		else if (cnt[i] == 0) {
			++cnt[i];
			path.push_back(i);
			bt(level + 1);
			path.pop_back();
			--cnt[i];
		}
		else {
			int len = path.size();
			if (len - i - 1 >= 0 && path[len - i - 1] == i) {
				++cnt[i];
				path.push_back(i);
				bt(level + 1);
				path.pop_back();
				--cnt[i];
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		ap.push_back(a);
	}
	sort(ap.begin(), ap.end());
	bt(0);
	if (!flag) cout << -1;
}