[백준] 15918-랭퍼든 수열쟁이야!!!(C++)

문제링크:www.acmicpc.net/status?user_id=gusdnr9875&problem_id=15918&from_mine=1

채점 현황

 

백트래킹 문제입니다. dfs를 통해 구현하는데 이때 문제 조건에 맞게 가지치기를 해주어야 합니다.

 

가지치기 

• 1. x,y가 주어지기 때문에 위치를 정할 수 있습니다. ex) x,y가 1,5라면 5 - 1 - 1 = 3. 즉 3이 x, y 위치에 고정됩니다.
• 2. 2*n개인 위치를 반복할때, arr[현재] 가 1이거나 arr[현재 + i + 1]이 이미 방문했을때는 탐색해줄 필요가 없습니다.
• 3. 2*n개인 위치를 반복할때, 현재 + i +1 > 2n 이면 탐색해줄 필요가 없습니다.

 

 

아래는 정답코드입니다. 위 조건 3개를 충족시키게 구현했습니다.

#include <iostream>
using namespace std;
int n, x, y;
int arr[26] = { 0, };
bool checked[25] = { 0, };
int result = 0;

void dfs(int cur) {
	if (cur == n*2) {
		result++;
		return;
	}
	if (arr[cur] == 0) {

		for (int i = 1; i <= n; i++) {
			if (checked[i] == 0) {
				if (cur + i + 1 <= 2 * n && !arr[cur+i+1]) {
					checked[i] = 1;
					arr[cur] = i;
					arr[cur + i + 1] = i;
					dfs(cur + 1);
					checked[i] = 0;
					arr[cur] = 0;
					arr[cur + i + 1] = 0;
				}
			}
		}
	}
	else
		dfs(cur + 1);
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> x >> y;
	
	arr[y] = y - x - 1;
	arr[x] = y - x - 1;
	checked[y - x - 1] = 1;
	dfs(1);
	cout << result << endl;
	return 0;
}