백준 15650번 : N과 M(2)

• 분류: 백트래킹

코드

#include <iostream>

int n, m;
bool visit[9];
int seq[9];

void dfs(int depth) {
    if(depth==m) {
        for(int a=0 ; a<m ; a++) {
            std::cout << seq[a] << ' ';
        }
        std::cout << "\n";
        return;
    }
    for(int i= (depth==0)?0 : seq[depth-1] ; i<n ; i++) {
        if(!visit[i]) {
            visit[i] = true;
            seq[depth] = i+1;
            dfs(depth+1);
            visit[i] = false;
        }
    }
}

int main() {
    std::cin >> n >> m;
    dfs(0);
}

• 코멘트
  
  간단한 dfs로 문제를 해결할 수 있고, 앞 문제 백준 15649번을 살짝 변형해서 해결할 수 있다. 앞 문제와는 다르게 오름차순인 수열만 출력해야 하므로,

    for(int i=0 ; i<n ; i++) {
  

  부분을

  for(int i= (depth==0)?0 : seq[depth-1] ; i<n ; i++) {
  

  과 같이 바꿔 준다. 단순히 시작 지점을 0에서 seq[depth-1], 즉 수열의 직전 원소부터로 바꾼 것이다.
  물론 depth==0이면 이전처럼 0부터 시작하면 되니, ternery operator로 간편하게 써 준다.