[백준] 15649번 N과 M (1) (C++) - backtracking

문제

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

코드

#include <iostream>

using namespace std;

int n, m;
int arr[9];
bool isVisited[9] = {false,};

void dfs(int cnt){
  if(cnt==m){
    for(int i=0; i<m; i++){
      cout << arr[i] << ' ';
    }
    cout << '\n';
    return;
  }
  for(int i=1; i<=n; i++){
    if(!isVisited[i]){
      isVisited[i] = true;
      arr[cnt]=i;
      dfs(cnt+1);
      isVisited[i] = false;
    }
  }
}

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

정리

backtracking?

백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 알고리즘

DFS의 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 곳을 검사하는 방법

백트래킹은 가지치기(Pruning)을 통해 효율을 극대화한다.

참조

https://cryptosalamander.tistory.com/54

https://velog.io/@mmindoong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking