백준 15666 c++ "N과 M (12)" -PlusUltraCode-

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

 

[필자 사고]

조합 문제다.

다만 필자가 잠시 난관에 부딪혔떤 부분은 1111, 1111 이런식으로 같은 수가 두번 출력되는 문제였다.

이걸 해결하기 위해 prevData를 이용하여 이전에 사용했떤 값이 같으면 이후 데이터는 고르지 않겠따. 와 같은 선언이다.

해당 부분만 해결하면 문제 없이 알고리즘을 해결했다.

 

아래는 자세한 코드해설이다.

[코드 해설]

Input() 함수

• 사용자로부터 정수 N과 M을 입력받는다.
  N: 전체 숫자의 개수, M: 뽑을 숫자의 개수
• 이어서 N개의 숫자를 입력받아 arr 벡터에 저장한다.
• 이후 조합의 정렬 순서를 보장하기 위해 arr을 오름차순 정렬한다.

이 함수는 전체 데이터 준비를 담당하며, 정렬은 DFS에서 중복 제거 및 사전순 출력을 위한 전처리이다.

---

DFS(int idx, int depth) 함수

• 현재까지 선택한 숫자의 개수인 depth가 M에 도달하면
  resultArr의 내용을 출력하고 함수를 종료한다.
• 그렇지 않은 경우, idx부터 N까지 반복하며 가능한 숫자를 선택한다.
• 같은 깊이에서 중복된 숫자가 여러 번 선택되는 것을 막기 위해
  prevData를 사용하여 직전에 사용한 값과 같은 값은 건너뛴다.
• 선택된 숫자는 resultArr에 추가하고, 현재 인덱스를 유지한 채 다음 깊이로 탐색을 이어간다.
  이는 같은 수를 여러 번 선택하는 중복 조합 구조를 구현하는 방식이다.
• 탐색 후에는 다시 숫자를 제거하여 백트래킹한다.

이 함수는 백트래킹 기반의 DFS로 모든 중복 조합을 생성하되, 동일 조합이 중복 출력되지 않도록 방지하는 역할을 한다.

---

Game_Start() 함수

• 조합 생성을 위한 DFS 탐색을 시작한다.
• 인덱스 0부터, 깊이 0으로 시작하여 가능한 조합을 모두 탐색하게 한다.

이 함수는 탐색의 진입점으로, 본격적인 조합 생성 로직을 시작하는 역할을 한다.

[소스 코드]

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

using namespace std;

int N, M;
vector<int> arr;
vector<int> resultArr;

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());
}

void DFS(int idx, int depth) {
	if (depth == M) {
		for (int i = 0; i < resultArr.size(); i++) {
			cout << resultArr[i] << " ";
		}
		cout << "\n";
		return;
	}
	int prevData = -1;
	for (int i = idx; i < N; i++) {
		if (prevData == arr[i])continue;
		resultArr.push_back(arr[i]);
		DFS(i, depth + 1);
		resultArr.pop_back();
		prevData = arr[i];
	}
}

void Game_Start() {
	DFS(0, 0);
}

int main(void) {
	Input();
	Game_Start();
}