[백준] 15650번 N과 M (2) C++

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/15650

 

 

15650번: N과 M (2)

 

 

이번 문제는 백트래킹(BackTracking) 문제였습니다. 

문제를 풀이하기 전에 백트래킹(BackTracking)이 무엇인지 알아보겠습니다.

 

 

 

백트래킹(BackTracking)

백트래킹(backtracking)이란, 모든 곳을 방문하여 노드의 개수가 많아질 때 비효율적일 수 있는 DFS에 가지치기(Prunung)를 통해 가도 되지 않는 루트는 고려하지 않고 탐색하는 완전 탐색 기법입니다.  문제를 해결하는 과정에서 유망하지 않은 노드라면 백트래킹(backtracking)을 수행하여 상위 노드로 되돌아가고, 유망한 노드라면 그 노드를 기준으로 DFS를 수행합니다. 

 

 

 

가지치기(Pruning)

가지치기(pruning)란, 불필요한 탐색 부분을 제거하는 것을 말합니다. 트리에서 나뭇가지를 치듯이 필요없는 가지를 쳐낸다고 생각하시면 쉽습니다. 가지치기(pruning)는 탐색 트리에서 최소극대화 알고리즘을 적용할 때 탐색하고 평가하는 노드를 줄이기 위해 사용됩니다.

 

 

 

 

 

《문제 풀이》

 

1. arr 배열의 0부터 시작하기 위해 메인함수에서 NandM(0) 호출

2. idx == 0 일 때는 아직 배열에 아무것도 저장하지 않은 상태이기 때문에 1~N 차례로 삽입

3. 1 <= idx 일 때는 arr[idx-1] + 1 부터 N 삽입(오름차순과 중복 방지를 위해)

4. 각 i에 대하여 NandM(idx + 1)을 수행

5. idx == M 이라면 arr[0] ~ arr[M-1] 출력  

 

 

 

《C++ 코드》

 

#include <iostream>

using namespace std;

int N, M;
int arr[8];

void NandM(int idx){
	if(idx == M){
		for(int i=0; i<M; i++){
			cout<<arr[i]<<" ";
		}
		cout<<"\n";
	}
	
	//idx가 0일 때는 1부터 삽입  
	if(idx == 0){
		for(int i=1; i<=N; i++){
			arr[idx] = i;
			NandM(idx + 1);
		}
	}
	//idx가 1 이상일 때는 전 배열값 + 1 부터 삽입    
	else{
		//오름차순과 중복 방지를 위해
		for(int i=arr[idx-1]+1; i<=N; i++){   
			arr[idx] = i;  
			NandM(idx + 1);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N>>M;
	NandM(0); //배열 0부터 시작  
	
	return 0;
}

 

개발 환경: Dev-C++

 

 

 

Baekjoon - 정답 화면