[C++] 백준 15650 : N과 M (2)
#include <iostream>
int arr[9]; // 순열 저장 배열
bool visited[9] = {false}; // 방문 여부
int N, M; // N개 중에 M개 고른 순열
void DFS(int cnt, int num){
if(cnt == M){ // M개의 순열 되었을 때
for(int i = 0; i < M; i++){
printf("%d ", arr[i]); // 순열 프린트
}
printf("\n");
return; // 프린트 후 반환 -> 재귀함수 완료
}
for(int i = 1; i <= N; i++){ // 1~N 까지 순열 탐색
if(!visited[i] && i > num){ // 방문되지 않은 수 일 때, 앞 수가 뒷 수보다 크게
visited[i] = true; // 방문 체크
arr[cnt] = i; // 순열 넣기
DFS(cnt + 1, i);
visited[i] = false; // 방문 초기화
}
}
}
int main(int argc, char** argv){
scanf("%d %d", &N, &M);
DFS(0, 0); // 0번째 순열
return 0;
}
백트래킹 연습용 문제
- 백트래킹이라고 해서 방문여부에 변화를 무조건 주어 문제를 풀 생각을 하지 않아도 좋다. 수학적으로 접근해도 괜찮다.
Author And Source
이 문제에 관하여([C++] 백준 15650 : N과 M (2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-15650-N과-M-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)