[백준] 15654번 N과 M (5) C++

 

 

 

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

 

 

15654번: N과 M (5)

 

 

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

백트래킹(backtracking)이 무엇인지 모르겠다면 이전 블로그를 참고해주세요 😊 

 

 

 

 

 

《문제 풀이》

 

1. N개의 수를 입력받을 arr 배열과 순열을 출력하기 위한 result 배열 선언

2. 중복 순열은 출력하면 안되므로 boolean 타입의 visited 배열 필요 

3. 사전 순으로 증가하는 순서로 출력하기 위해 sort 함수로 오름차순 정렬 

4. result 배열에 저장되지 않은 수라면 result 배열에 저장하고, 아니라면 저장하지 않음

5. result 배열에 저장되지 않았을 경우, 재귀 호출 후에 visited[i] = false 해줌

 

 

 

 

 

《C++ 코드》

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 8;

int N, M;
int arr[MAX];
int result[MAX];
bool visited[MAX]; //중복 순열 방지  

void NandM(int idx){
	if(idx == M){
		for(int i=0; i<M; i++){
			cout<<result[i]<<" ";
		}
		cout<<"\n";
		return; //(1) 
	}

	for(int i=0; i<N; i++){
		//result 배열에 저장되지 않았다면  
		if(!visited[i]){ 
			result[idx] = arr[i];
			visited[i] = true;
			NandM(idx+1);
			visited[i] = false; //(2)
		}
	}
}

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

	cin>>N>>M;
	
	for(int i=0; i<N; i++)
		cin>>arr[i];
	
	//사전 순으로 증가하는 순서로 출력하기 위해 정렬
	sort(arr, arr+N);   
	NandM(0);
		
	return 0;
}

 

개발 환경: Dev-C++

 

 

 

Baekjoon - 정답 화면