백준 15663 c++ "N과 M (9)" -PlusUltraCode-

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

 

[필자 사고]

조합 문제인줄 알았지만 순서가 정해져 있는 문제이다.

조합에서는 DFs인자에 한상 현재 idx 및 size 를 넘겨줬지만

순서가 정해져있으면 idx를 넘기지 않고 size만 넘기면 된다.

 

그후 visited배열을 통해 왔떤 거 방문 처리를 해주고

이미 배열이 정렬되어 있는 상황이니깐 같은 깊이에서 똑같은 숫자를 고르는건 무의미하다.

결국에는 prevData를 이용하여 같은 숫자를 고른거는 방지해주는 장치를 마련하고 문제를 해결한다.

resultArr.push_back() 해주는거랑 resultArr.pop_back() 해주는건 잊지 말자

 

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

[코드 해설]

 

• Input() 함수
  • 사용자로부터 두 개의 정수 N과 M을 입력받는다.
  • 이어서 N개의 정수를 입력받아 arr 벡터에 저장한다. 이는 사용할 숫자들의 리스트이다.
• DFS(int depth) 함수
  • 깊이 우선 탐색 방식으로 M개의 수열을 생성한다.
  • 현재 깊이가 M에 도달하면 resultArr에 저장된 수열을 출력한다.
  • 이전에 사용한 수를 추적하여 중복되는 수열이 생성되지 않도록 한다.
  • visited 배열을 사용하여 현재 탐색 경로에서 중복된 원소를 선택하지 않도록 제어한다.
• Game_Start() 함수
  • arr를 오름차순으로 정렬한다. 이는 중복 수열을 방지하고 사전순 출력을 보장하기 위함이다.
  • visited와 resultArr을 초기화하고, DFS(0)을 호출하여 수열 생성 탐색을 시작한다.
• main() 함수
  • Input()을 호출하여 입력을 받고,
  • Game_Start()를 호출하여 문제 해결을 수행한다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

void DFS(int depth) {
	if (depth == M) {
		for (int i = 0; i < resultArr.size(); i++) {
			cout << resultArr[i] << " ";
		}
		cout << '\n';
		return;
	}

	int prevNum = -1;
	for (int i = 0; i < N; i++) {
		if (visited[i])continue;
		if (prevNum == arr[i])continue;
		visited[i] = true;
		resultArr.push_back(arr[i]);
		DFS(depth+1);
		resultArr.pop_back();
		visited[i] = false;
		prevNum = arr[i];

	}
}

void Game_Start() {
	sort(arr.begin(), arr.end());
	visited.clear();
	resultArr.clear();
	visited.resize(N, false);
	DFS(0);

}

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