[백준] 15649번: N과 M (1)

 

 

---

 

문제

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

 

 

개념

백트래킹

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 1부터 n까지의 숫자를 수열에 입력 가능
// m = 재귀 수행할 깊이
int n, m;
vector<int> v;
bool visited[9];  // n이 최대 8이므로

// 백트래킹을 수행할 함수
void backtracking(int depth) {
  if (depth == m) {
    for (int i = 0; i < m; i++) {
      cout << v[i] << " ";
    }
    cout << "\n";
    return;
  }

  for (int i = 1; i <= n; i++) {
    // 중복 제거하기 위해 방문했는지 체크
    if (!visited[i]) {
      visited[i] = true;        // 선택
      v.push_back(i);           // 수열에 추가
      backtracking(depth + 1);  // 다음 깊이로 재귀 호출
      visited[i] = false;       // 선택 취소
      v.pop_back();             // 수열에서 제거
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> n >> m;

  backtracking(0);

  return 0;
}

 

 

 

 

코드 설명

다음과 같은 변수를 입력 받는다.

n = 수열에 입력할 1부터 n까지의 수, i로 늘려감
m = 중복없이 고를수 있는 숫자의 개수

 

문제의 입출력을 통해 규칙을 찾아보면 주어진 수로 만들 수 없는 중복 조합을 찾는 문제이다.

즉, 달리 말하면 재귀 트리 중 전위 순회(Preorder Treversal) 문제라고도 할 수 있다.

하지만 한번 방문한 노드는 다시 방문하지 않도록 해야 한다.

 

이를 위해 backtracking이라는 함수와 bool 타입의 변수 visited를 만들었다.

백트래킹 함수는 해당 depth에 있는 노드를 방문하면서 숫자를 출력한다.

이때, visited 변수 조건이 없다면 중복을 허용한 일반적인 전위 순회겠지만

문제에서 중복을 제거하라고 요구했으므로 다음 깊이로 재귀 호출하기 전 방문 처리를 해준다.

 

 

 

 

---