[백준] 15663번 N과 M(9)

문제: 15663번: N과 M (9)

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int n, m;
int curNums[8]; // max 가 8
int nums[8]; // max 가 8
int used[8]; // 해당 인덱스 사용 여부(숫자 중복 허용)


void Funct(int functM) {
	if (m == functM) {
		for (int i = 0; i < m; i++)
			cout << curNums[i] << " ";
		cout << "\n";
		return;
	}

	set<int> curUseNums; // 현재 단계에서 다음 단계로 갈 때 쓴 애들 목록(목록에 있으면 안 쓸 것)
	
	// 아직 수열이 다 안 찼으면 재귀..
	for (int i = 0; i < n; i++) {
		// 만약 집합에 있으면 패스
		// 또는 해당 인덱스 요소를 이미 사용했으면 패스
		if (used[i] == 1 || curUseNums.find(nums[i]) != curUseNums.end()) continue;

		used[i] = 1; // 해당 인덱스 요소 사용 표시
		curNums[functM] = nums[i];
		curUseNums.insert(nums[i]); // 집합에 넣기

		Funct(functM + 1);

		used[i] = 0; // 해당 인덱스 요소 사용 표시 없애기
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> nums[i];
	sort(nums, nums + n); // 오름차수 정렬

	Funct(0);

	return 0;
}

 

이번엔 조금 생각해야 하는 문제였다.

 

입력으로 같은 수가 존재하는 수열이 들어오는 경우가 있다. 이러한 경우에 중복되지 않는 수열을 출력해야 하는데 처음엔 살짝 멈칫했다.

 

현재 단계에서 다음 단계로 넘어가기 전에 curNums 에 수를 넣는다. 다음 단계로 갈 때 curNums 에 집어넣는 수를 현재 단계의 집합에 넣는다. 만약 다음 단계로 갈 때 집어넣으려고 하는 수가 이미 집합에 있다면 그 경우에는 curNums 에 넣지 않고 continue 한다.

 

만약 현재 단계에서 다음 단계로 넘어갈 때 넣으려고 하는 수가 9라고 해보자. 근데 만약에 현재 단계 집합에 9가 이미 들어있다는 것은 뭘 의미하는걸까? 9 로부터 시작되는 모든 분기를 보고 왔음을 의미한다. 즉, 이미 set 에 9가 있는 상황에서 또 9를 curNums 에 넣으려고 하면 중복되는 수열이 생기니까 이를 막기 위해 집합을 이용한 것이다.

 

그리고 이 문제에서는 방문처리를 nums[i] 를 가지고 하는게 아니라 i 를 가지고 한다. 이유는 입력으로 똑같은 값이 주어지는 경우가 있는데 nums[i] 로 방문처리를 해버리면 같은 값이지만 다른 객체라도 같은 취급을 받아서 바로 빠져나가버리기 때문이다.

 

즉, 중복을 허용하기 위해 nums[i] 값 대신 i 라는 인덱스를 가지고 방문처리를 한 것이다. 

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹