[C++] 백준 15649 : N과 M (1)
#include <iostream>
int arr[9] = {0}; // 최대 8개
bool visited[9] = {false}; // 방문 여부
int N, M; // N개 중 M개 고른 수열
void DFS(int cnt){
if(cnt == M){ // M개가 골라졌을 때
for(int i = 0; i < M; i++){
printf("%d ", arr[i]); // arr에 저장된 수 출력하기
}
printf("\n");
return;
}
// M개 아닌 경우
for(int i = 1; i <= N; i++){ // 1~N까지의 모든 수 탐색
if(!visited[i]){ // 방문된 적이 없으면
visited[i] = true; // 방문 체크
arr[cnt] = i; // 순열 추가
DFS(cnt+1); // 다음 순열 고르기
visited[i] = false; // 방문 초기화 - 재귀 함수 끝나면 호출됨
}
}
}
int main(int argc, char** argv){
scanf("%d %d", &N, &M);
DFS(0);
return 0;
}
백트래킹 연습용 문제. 사실상 인터넷보고 공부하면서 풀었다. 아직 바보라서 보고 바로 백트래킹이라는 것을 떠올리지도 못했고, 힌트를 보고서도 백트래킹 구현하는 뾰족한 수가 생각나지 않아서 기본적으로 다들 짜는 코드 스타일을 공부하고 다시 짜보았다. 아직 내 것으로 만드는 시간이 필요하겠지만 우선은 암기뿐이다
Author And Source
이 문제에 관하여([C++] 백준 15649 : N과 M (1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-15649-N과-M-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)