[BOJ15649 C++] N과 M (1)

백트래킹 입문서 N과 M.. (시리즈)

순열과 조합 관련 개념 익히기도 좋다.

순열 - 순서가 존재하기 때문에, {1, 2, 3} 이나 {2, 1, 3} 이나 다른 것으로 본다.

조합 - 순서는 존재하지 않고 구성 요소만 확인

N과 M은 .. 순열이지?

{1, 2, 3, 4}나 {4, 3, 2, 1} 이나 다르게 보니까

백트래킹에서는 DFS나 이런 기술을 좀 쓰는 것 같다.

DFS가 근데 진짜 트리나 그런걸로 구현하는건 아니고, visited[] 나 selected[] 뭐 이런걸로 대체해서 하더라고

여기서 중요한건 재귀 사용 방법. . + 그리고 출력이 중요하니 vector로 넣는 방법 + 함수를 이용하니 편리하게 전역변수 쓰기

아래의 코드는 "조합" 일 경우 다 출력하는 방법.

여기서 조금만 고치면 순열로 바뀌고, 매커니즘은 비슷하니까 이거부터 이해하고 가자

int MAX; //MAX는 cin 으로 입력으로 받는다.
int CNT_MAX; //이것도 입력으로! DFS 함수 내에서 사용되니 전역으로 하면 편해~
bool select[10];
int Arr[10];
void Print(){
	for(int i = 0; i < MAX; i++){
    	if(select[i]){
        	cout << Arr[i] << " ";
        }
    cout << endl;
}

void DFS(int idx, int cnt){
	if(cnt == CNT_MAX){
    	Print();
        return;
    }
    for(int i = idx; i < MAX; i++){ //"조.합" 이기 때문에, i = idx 로 시작을 한다. 뒤에 것들을 안본다는 의미
    	if(select[i]) continue;
        select[i] = true;
        DFS(i, cnt+1);
        select[i] = false;
    }
}

int main(){
	MAX 까지 받고, Arr에 값넣고, select 초기화 하고 등등
    DFS(0, 0);
}

이렇게 구성되는데, idx = 0, cnt = 0 으로 들어가서, select로 켰다 껐다 하면서 착착 하는 것.

근데 이 문제에서 원하는건 조합이 아니잖아?

순열로 바꿔줘야지

vector<int> vec;

void Print(){
    for(int i = 0; i < vec.size(); i++){
            cout << vec[i] << " ";
    }
    cout << '\n';
    return;
}

void DFS(int cnt){
    if(cnt == CNT_MAX){
        Print();
        return;
    }

    for(int i = 0; i < MAX; i++){ //"순.열" 이라 i가 idx부터 시작하지 않고, 0부터 다 본다~
        if(Select[i]) continue;
        Select[i] = true;
        vec.push_back(Arr[i]);
        DFS(cnt+1);
        vec.pop_back();
        Select[i] = false;
    }

}

여기서는 i = idx로 시작하지 않는 것과,
조합에서는 항상 오름차순으로 Print를 하게 한 것과 다르게,
vector를 이용해서 select 된 순으로 추가하기 때문에 수열이 "사전 순"으로 증가하는 것으로 출력할 수 있다.

vector안에서 차례되면 넣고 빼고 하는거지.

이게 포맷이 좀 비스무리해서 그냥 손에 익혀두는 게 맘이 편할 것 같다.

아 그리고 또 하나 안 것.
endl 쓰니까 시간초과나고 '\n' 쓰니까 시간초과 안나더라 ....