[G5] 백준 23284번 모든 스택 수열 C++ 백트래킹

리뷰

 

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

문제를 이해하는데 오랜 시간이 걸렸다.

 

 

전역 변수

• n : 수열의 크기를 저장할 변수
• push : 스택을 구현할 벡터
• pop : 스택에서 pop한 정수를 저장할 벡터

 

함수

1. bt

void bt(int level) {
	if (level > n && push.empty()) {
		print();
		return;
	}

	if (!push.empty()) {
		int b = push.back();
		pop.push_back(b);
		push.pop_back();
		bt(level);
		push.push_back(b);
		pop.pop_back();
	}

	if (level <= n) {
		push.push_back(level);
		bt(level + 1);
		push.pop_back();
	}
}

 

스택에 수를 쌓아가며 pop을 할지 push를 할지, 출력 할지를 분기처리하는 함수

 

2. print

void print() {
	for (int i = 0; i < n; ++i) {
		cout << pop[i];
		if (i != n - 1) cout << " ";
	}
	cout << "\n";
}

 

pop된 요소를 순서대로 출력하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, bt함수에 1을 매개변수로 전달하여 호출한다.
2. bt함수에선 현재 정수를 변수 level로 전달받는다.
3. 기저 조건으로 level이 n을 초과했고, push가 빈 상태라면 print함수를 호출한다.
4. print함수는 pop벡터의 요소를 출력한다.
5. print함수 호출을 마친 후 리턴 처리한다.
6. push가 비지 않았다면 push의 맨 뒤 요소를 pop에 추가하고, push의 맨 뒤 요소를 제거한다.
7. bt함수에 level을 그대로 전달하여 호출한다.
8. 재귀를 빠져나온 뒤엔 push와 pop벡터에 수행한 연산을 원상 복구시킨다.
9. level이 n이하라면 push에 level을 추가하고, bt함수에 level+1을 전달하여 호출한다.
10. 재귀를 빠져나온 뒤엔 push에 추가한 요소를 원상 복구시킨다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 모든 스택 수열을 한 줄에 하나씩 사전 순으로 출력해야 하기에 level을 사용해 순서대로 재귀를 수행했다.
2. 마지막 요소의 경우 공백을 포함하면 WA를 받는다, 따라서 n-1인덱스 수행 후엔 공백을 추가하지 않아주었다.

 

정답 코드

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

int n;
vector<int> push;
vector<int> pop;

void print() {
	for (int i = 0; i < n; ++i) {
		cout << pop[i];
		if (i != n - 1) cout << " ";
	}
	cout << "\n";
}

void bt(int level) {
	if (level > n && push.empty()) {
		print();
		return;
	}

	if (!push.empty()) {
		int b = push.back();
		pop.push_back(b);
		push.pop_back();
		bt(level);
		push.push_back(b);
		pop.pop_back();
	}

	if (level <= n) {
		push.push_back(level);
		bt(level + 1);
		push.pop_back();
	}
}

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

	cin >> n;
	bt(1);
}