boj 15666 - N과 M (12) BackTracking

문제를 풀때 코드를 입력하기 전 알고리즘을 먼저 설계해야 한다는 후임의 말을 듣고 

피드백을 반영하여 먼저 생각하는 연습을 진행하였다.

 

조건

1.각 입력들이 무엇을 의미하는지에 대해서 먼저 생각하기 n, m, list

2. 문제 조건에서 비내림차순 형태( 사전순으로 증가) 

3. 같은 수를 여러번 골라도 된다 

4. 중복되는 수열을 여러번 출력하면 안된다

 

해당 문제에 대하여 전체적으로 처음에 설계한 부분은 다음과 같다. 

 

알고리즘 설계 

1. 입력

2. list에 대해서 오름차순 정렬

3. dfs에 들어가야할 인자 먼저 생각

(정렬된 리스트, 탐색하면서 값이 집어넣어질 빈 컨테이너, 시작index, 리스트 개수 n , 출력 개수 m )

4. dfs를 사용하는 이유는 M의 수열을 한 칸씩(단계별) 선택하며 만들어 가야 하므로 

5. 시작 index인 start는 0으로 설정

6. 해당 단계에서 컨테이너에 집어넣어 질 수 있는 후보는 start ~ n  / for(int i=start; i<n; i++)

7.dfs로 넘기는 시작 index는 i다.

8. 같은 단계에서는 이미 출력한 수라면 출력해선 안됨 -> 이전 출력한 상태를 저장하는 변수인 ref를 설정 / 이미 오름차순 정렬 되어 있으므로 현재의 ref보다 더 작은수는 뒤에 존재하지 않음

또한 정렬되어 있으므로 만약 같은 값이 존재한다면 연속해서 등장하게 됨 

9. ans에 저장할 값에 대해서index로 저장할지, 값 그자체로 저장할지에 대해서 선택

10. 길이가 m이 되면 출력 하기 

 

1. 상태
재귀 함수 하나가 표현하는 상태가 뭔지.
현재까지 만든 수열 ans
이번 depth에서 고를 수 있는 시작 위치 start

2. 선택
지금 상태에서 무엇을 선택할 수 있는지.
i = start ~ n-1 중 하나를 고른다

3. 제약
선택할 때 어떤 걸 막아야 하는지.
비내림차순: 다음 선택은 start=i
같은 depth 중복 제거: 같은 값이면 skip

4. 종료 조건
언제 답으로 인정되는지.

ans.size() == m

 

void dfs(const vector<int> &list, vector<int> &ans, int start, int n, int m)
{
	int ref = -1;
	
	if(ans.size()==m)
	{
		for(int i=0; i<ans.size(); i++)
		{
			cout<<list[ans[i]]<< (i==ans.size()-1? "\n" : " ");
		}
		return;
	}

	for(int i=start; i<n; i++)
	{
		if(list[i] ==ref) continue;

		ans.push_back(i);
		ref = list[i];
		dfs(list,ans,i,n,m);
		ans.pop_back();
	}
}

생각을 코드로 구현하다 막혀서 이전의 안좋은 습관이 발동하여 값을 하나씩 지우고 컴파일 하고 하는

행동을 하였는데 

차분하게 다시 생각하여 

index부터 먼저 출력 한 후, 이를 가지고 index -> 값을 출력 해 보면서 내가 하는 동작에 대해서 

다시한번 명확하게 규정한 다음 

상태 변수를 추가하여 중복 처리되는것을 방지하는 방식으로 문제를 전개 해 나갔다. 

 

처음에 헷갈렸던것은

ans에 입력받을 수를 index로 넣어야 할지 값으로 넣어야 할지를 확정하지 못했고 

사전에 초기조건을 처리하는데 있어서 ref 변수의 초기화를 -1로 설정하는 것을 망각하였다. 

 

ans에 index를 넣게 되면 출력 시 list에 다시 해당 index를 집어 넣어서 출력해야 하므로 생각을

이중으로 처리하기 되니, 아얘 처음부터 값을 집어 넣어서 처리하도록 하는 것이 생각에 친화적으로 

생각 과정을 줄일 수 있는 방법이라고 생각이 들었다. 

 

또한, ref=-1은 현재 문제가 자연수이기 때문에 가능한 조건으로, bool 변수를 초기에 두어

start = true로 해서 처음 dfs에 들어갔을때는 start 발동하고, 이후에는 false로 처리하여 

초기 조건을 해결할 수 있을 것으로 보인다.

int ref = 0;
bool first = true;

for (int i = start; i < n; i++) {
    if (!first && list[i] == ref) continue; 
    //초기에는 first =  true이므로 !first = false,
    //이후에는 !first는 ture 확정
    first = false;
    ref = list[i];
    ...
}

 

 

 

전체 코드

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

using namespace std;


void dfs(const vector<int> &list, vector<int> &ans, int start, int n, int m)
{
	
	int ref = -1;
	
	if(ans.size()==m)
	{
		for(int i=0; i<ans.size(); i++)
		{
			cout<<ans[i]<< (i==ans.size()-1? "\n" : " ");
		}
		return;
	}

	for(int i=start; i<n; i++)
	{
		if(list[i] ==ref) continue;

		ans.push_back(list[i]);
		ref = list[i];
		dfs(list,ans,i,n,m);
		ans.pop_back();
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin>>n>>m;

	vector<int> list(n);

	for(int i =0; i<n; i++)
	{
		cin>>list[i];
	}

	sort(list.begin(), list.end());

	
	int start = 0;

	vector<int> ans;
	
	dfs(list, ans, start, n, m);

	
}