[백 트래킹] BOJ 15652 N과 M (4)

www.acmicpc.net/problem/15652

15652번: N과 M (4)

문제 해결 알고리즘

1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다.

 

2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다.

   같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다.

   (func함수는 이 배열에 있는 원소들이 비내림차순으로 정렬되어 있는지 확인해주는 함수이다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int N,M;
int arr[8];

bool func(){
  bool flag = true;
  for(int i=0;i<M-1;i++){
    if(arr[i] > arr[i+1]) {
      flag = false;
      break;
    }
  }
  return flag;
}

void dfs(int n){
  if(n == M){
    if(func()){
      for(int i=0;i<M;i++){
        cout << arr[i] << " ";
      }
      cout << "\n";
    }
    return;
  }
  for(int i=1;i<=N;i++){
    arr[n] = i;
    dfs(n+1); 
  }
}

int main(){
  cin >> N >> M;

  dfs(0);

}