백준 15654 N과 M (5) C++

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

15654번: N과 M (5)

 

복기

내가 가장 취약한 재귀 및 백트래킹분야이므로 이쪽 문제들은 다 정리하면서 복기해보는걸로 함

 

DFS랑 비슷한데 방문한 갯수가 M개가 되는 순간 백트래킹한다 정도로 생각하고

일단 입력 다 받고 count = 0으로 재귀 시작

 

재귀 입장해서 count 0이므로 출력 안하고 값을 넣음

해당 값이 들어가있는지 확인해야하므로 visited 사용

!visited[i]라면 temp[count] = vec[i]로 값을 넣어주고 visited[i] = true;

그리고 나서 for문을 도는게 아니라 재귀를 또 들어감 => 이게 핵심인데 이게 도저히 자연스럽게 느껴지지가 않음

 

그냥 반복문을 돌면 다음 값이 들어가는데까진 쉽겠지만 다시 한단계 앞으로 돌아오는게 구현이 복잡해짐

또 이중으로 이미 방문되었는지 카운트해야하고 이미 출력되었는지 확인해야하고...

 

그러니 한단계 돌아오는게 필요하다면 재귀로 백트래킹한다고 생각하면 일단 떠오르긴 할 듯 한데

취약한 분야이다보니 여전히 직관적이지가 않아서 비슷한 류 문제 다 풀어봐야 할 듯

 

정답코드

#include <bits/stdc++.h>
using namespace std;

vector<int> vec, temp;
vector<bool> visited;
int N, M;
void recursion(int count)
{	
	if (count == M) {
		for (int t : temp) { cout << t << ' '; }
		cout << '\n';
		return;
	}
	
	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			visited[i] = true;
			temp[count] = vec[i];
			recursion(count + 1);
			visited[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> M;
	vec.resize(N);
	temp.resize(M);
	visited.resize(N);

	for (int i = 0; i < N; i++) { cin >> vec[i]; }
	sort(vec.begin(), vec.end());

	recursion(0);

	return 0;
}