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

🥈 Silver 3 N과 M (1) 문제풀이

문제설명

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

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

---

C++ 풀이

#include <iostream>

using namespace std;

int n, m;
int number[9];
bool visited[9];

void dfs(int a)
{
    if (a == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << number[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            number[a] = i;
            dfs(a + 1);
            visited[i] = false;
        }
    }
}

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

---

추가 설명

백트래킹이라는 새로운 알고리즘이 등장한다.
백트래킹은 DFS를 이용하여 모든 경우의 수를 찾되, 조건에 맞지 않으면 즉시 중단하고 이전으로 돌아가서 다시 찾는 알고리즘이다.
N과 M 시리즈는 대표적인 백트래킹 연습문제이므로, 하나하나 다 풀어보려고 한다.

문제에서 원하는 수열이라 함은, 결국 N개의 수에서 중복없이 M개를 찾아내는 '순열'인 셈이다.
다만, 중복은 허용하지 않기에 visited 배열에서 중복 여부를 검사하게 구성하였다.