[G5] 백준 12980번 좋아하는 수열 C++ 백트래킹

리뷰

 

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

오랜만에 풀어본 쉽고 재미있는 백트래킹 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 순열의 크기를 저장할 변수
• s : 목표 점수를 저장할 변수
• ans : 목표 점수와 일치하는 순열의 개수를 저장할 변수
• arr : 칠판에 적혀있는 순열 정보를 저장할 정수형 배열
• visit : 숫자를 사용했는지 여부를 저장할 논리형 배열
• can_use : 0에 들어올 수 있는 숫자를 저장할 정수형 벡터

 

함수

1. Print

void Print( int cnt, vector< int >& maked )
{
	for ( int d : maked )
	{
		cout << d << " ";
	}
	cout << "cnt: " << cnt << '\n';
}

 

디버깅용 함수

 

2. BackTracking

void BackTracking( int level, int cnt, vector< int >& maked )
{
	//Print( cnt, maked );

	if ( cnt > s )
		return;

	if ( level == n )
	{
		if ( cnt == s )
			++ans;

		return;
	}

	if ( arr[ level ] )
	{
		int add = 0;
		for ( int i = 0; i < static_cast< int >( maked.size() ); ++i )
		{
			if ( maked[ i ] < arr[ level ] )
				++add;
		}

		maked.push_back( arr[ level ] );
		BackTracking( level + 1, cnt + add, maked );
		maked.pop_back();
		return;
	}

	for ( int d : can_use )
	{
		if ( visit[ d ] )
			continue;

		int add = 0;
		for ( int i = 0; i < static_cast< int >( maked.size() ); ++i )
		{
			if ( maked[ i ] < d )
				++add;
		}

		visit[ d ] = true;
		maked.push_back( d );
		BackTracking( level + 1, cnt + add, maked );
		maked.pop_back();
		visit[ d ] = false;
	}
}

 

백트래킹을 통해 만들 수 있는 모든 수열을 찾고 개수를 구하기 위한 함수

 

 

문제풀이

1. n, s값을 입력 받고, n개의 수를 입력 받아 arr, visit배열을 초기화한다.
2. 1~n을 순회하며 visit이 false인 인덱스를 can_use에 push하여 초기화한다.
3. 빈 정수형 벡터 maked를 초기화 하고, BackTracking함수에 0, 0, maked를 매개변수로 전달하여 호출한다.
4. BackTracking함수 내부에선 변수 level, cnt, maked에 매개변수를 파싱하여 저장한다.
5. 첫 번째 기저 조건으로 cnt가 s보다 커졌을 경우 더 이상 탐색할 필요가 없으므로 return한다.
6. 두 번째 기저 조건으로 level이 n이 도달한 경우 cnt가 s와 같다면 ans를 증가시키고 여부와 상관 없이 return한다.
7. 세 번째 기저 조건으로 arr[level]이 0이 아닌 경우 level, cnt, maked를 갱신 후 재귀를 수행한다.
8. 재귀를 수행한 후엔 maked에서 추가한 요소를 pop해주고 return한다.
9. 위 기저 조건들에 해당하지 않는다면 can_use를 순회하며 사용할 수 있는 정수를 찾는다.
10. 사용한 수를 방문처리 후 level, cnt, maked를 갱신 후 재귀를 수행한다.
11. 재귀를 수행한 후엔 maked에서 추가한 요소를 pop, 사용한 정수에 방문을 해제한다.
12. 최종적으로 ans에 저장된 수를 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 칠판에 적혀있는 순열은 1보다 크거나 같고, N보다 작거나 같은 수가 한 번씩 등장하는 순열이다.
2. 지워져 있는 수는 0으로 주어지고, 5개 이하이다.
3. 0이 등장했을 때에만 사용할 수 있는 수에서 선택 후 대입하여 재귀를 수행해 주면 된다.
4. 0이 아닌 경우에도 점수를 체크해 주어야 한다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

const int N = 101;
int n, s, ans;
int arr[ N ];
bool visit[ N ];
vector< int > can_use;

void Print( int cnt, vector< int >& maked )
{
	for ( int d : maked )
	{
		cout << d << " ";
	}
	cout << "cnt: " << cnt << '\n';
}

void BackTracking( int level, int cnt, vector< int >& maked )
{
	//Print( cnt, maked );

	if ( cnt > s )
		return;

	if ( level == n )
	{
		if ( cnt == s )
			++ans;

		return;
	}

	if ( arr[ level ] )
	{
		int add = 0;
		for ( int i = 0; i < static_cast< int >( maked.size() ); ++i )
		{
			if ( maked[ i ] < arr[ level ] )
				++add;
		}

		maked.push_back( arr[ level ] );
		BackTracking( level + 1, cnt + add, maked );
		maked.pop_back();
		return;
	}

	for ( int d : can_use )
	{
		if ( visit[ d ] )
			continue;

		int add = 0;
		for ( int i = 0; i < static_cast< int >( maked.size() ); ++i )
		{
			if ( maked[ i ] < d )
				++add;
		}

		visit[ d ] = true;
		maked.push_back( d );
		BackTracking( level + 1, cnt + add, maked );
		maked.pop_back();
		visit[ d ] = false;
	}
}

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

	cin >> n >> s;
	for ( int i = 0; i < n; ++i )
	{
		cin >> arr[ i ];
		visit[ arr[ i ] ] = true;
	}

	for ( int i = 1; i <= n; ++i )
	{
		if ( !visit[ i ] )
			can_use.push_back( i );
	}

	vector< int > maked;
	BackTracking( 0, 0, maked );

	cout << ans;
}