[코딩 테스트] Backtracking > N과 M (1)

0. 링크

     백준 문제 링크

1. 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 입력

  첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 출력

  • 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예시

input	output
3 1	1 2 3
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

2. 해설

1. 중복을 허용하지 않는 순열을 고르기 위한 visited 벡터 선언
2. M개의 수를 갖는 순열을 만들기 위한 list 벡터 선언
3. Backtracking()함수 내에서 아래와 같이 반복한다.

   1) list.size() == m 이면 return후 출력
   2) i = 1; i <= N인 동안 다음을 반복한다.

   (1) !visited[i]일 경우

   (2) visited[i] = true
   (3) list.push_back(i)
   (4) Backtracking()
   (5) list.pop_back()
   (6) visited[i] = false // 2와 6을 통해, (1, 1)은 불가능하도록, (2, 1)과 (3, 1)은 가능하게 한다.

3. 코드

#include <iostream>
#include <vector>

using namespace std;

int n,m;
vector <int> list;
vector <bool> visited;

void print()
{
    for(size_t i = 0; i < list.size(); i++)
    {
        cout << list[i] << " ";
    }
    cout << '\n';
}

// 중복을 허용하지 않는 순열을 만들기
void Backtracking()
{
    if(list.size() == m)
    {
        print();
        return;
    }
    
    for(size_t i = 1; i <= n ; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            list.push_back(i);
            Backtracking();
            list.pop_back();
            visited[i] = false;
        }
    }
}

int main()
{
    cin >> n >> m;
    visited = vector<bool>(n+1, false);
    Backtracking();
}

4. 감상

     코테 스터디 시간에 풀어본 문제다. 백트래킹의 개념을 이해하는 문제였다. 앞으로 이어지는 두 개의 시리즈도 비슷하지만 다른 유형을 다룬다. 나를 위해 혹은 이 글을 보는 당신에게 도움이 될 백트래킹 시리즈 모음이다.