[백준/c++] - 15650 N과 M(2)

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

15650번: N과 M (2)

 백트래킹에 대해 공부하면서 풀었던 문제입니다.

 

N과 M(1)과 다른점이라면 중복된 수열을 제외하고 출력한다는 점입니다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int M;

vector<int>ans;
vector<vector<int>>ans_check;
vector<int>ans_tmp;


void backTracking(vector<int>&arr, vector<bool>&visited, int count) {

	if (count == N) { // 깊이가 충족되면 재귀 종료

		copy(ans.begin(), ans.end(), ans_tmp.begin());
		sort(ans_tmp.begin(), ans_tmp.end()); // 정렬 후 비교

		for (int i = 0; i < ans_check.size(); i++) {
			if (equal(ans_tmp.begin(), ans_tmp.end(), ans_check[i].begin()))  // 중복될 경우 스킵
				return;
		} 
		
		for (int& i : ans) {
			cout << i << ' ';
		}
		ans_check.push_back(ans);
		cout << '\n';

		return;
	}

	for (int i = 0; i < M; i++) {
		if (visited[i] == true)
			continue;
		else {

			visited[i] = true;
			ans[count] = i + 1;

			backTracking(arr, visited, count + 1);
			visited[i] = false;
		}


	}
}

int main() {

	vector<int>arr;
	vector<bool>visited;

	
	cin >> M;
	cin >> N;

	arr.resize(M);
	ans.resize(N);
	ans_tmp.resize(N);
	visited.resize(M);

	for (int i = 0; i < M; i++) {
		arr[i] = i + 1;
	}


	backTracking(arr, visited, 0);

	return 0;
}

N과 M(1)과 동일한 코드로 구성하고, 

재귀의 종료 조건에 중복된 수열이면 결과를 출력하지 않고 종료하라는 조건을 추가하였습니다.

 

다만, 수열을 비교할 때, 먼저 수열을 정렬하고 비교를 해야하는데,

만약 이번에 구한 답을 직접적으로 정렬하므로써 수정을 해버리면

결과값이 이상하게 나올 수 있습니다.

 

예를 들어 3 3 의 결과값을 출력한다고 했을때,

2 1 3 이후에 2 3 1 수열이 나와야 정상이지만,

2 1 3을 정렬하면 1 2 3 이되어, 다음 수열이 1 3 1 이라는 엉뚱한 값이 나오게 됩니다.

 

이는 코드상으로는 이미 첫 번째 원소로 2를 가지고 있다고 판단하기 때문에 발생하는 문제 입니다.

따라서 직접적으로 값을 수정할 게 아니라, 비교용 배열을 하나 더 선언 해서 이 배열을

정렬하고 비교하는 방법으로 해결할 수 있었습니다.