[백 트래킹] BOJ 15655 N과 M (6)

www.acmicpc.net/problem/15655

15655번: N과 M (6)

문제 해결 알고리즘

 

1. N과 M 값을 입력을 받고 주어진 수들을 벡터(v)에 저장한 다음 정렬해주고 dfs()함수를 실행해준다.

 

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

   같지 않다면 배열에 벡터(v)에 저장되어 있는 수들을 배열에 각각 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다.

   (func함수는 이 배열에 있는 원소들 중 중복된 것이 있는지, 오름차순인지 확인해주는 함수이다.)

 

소스 코드

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

int N, M; 
int arr[9], v[9];

bool func(){

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

  for(int i=0;i<M-1;i++){
    if(arr[i] > arr[i+1]) flag = false;
  }
   
  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 j=0;j<N;j++){
    arr[n] = v[j];
    dfs(n+1);
  }
}

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

  for(int i=0;i<N;i++){
    cin >> v[i];
  }

  sort(v, v+N);
  
  dfs(0);

}