[C++] Boj 15649 N과 M (1)

문제 링크

N과 M (1)

 

우선 나는 백 트래킹을 연습하려는 의도로 이 문제를 풀어 보았다. 

 

여기서 백 트래킹이란?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 게임으로 비유하자면 현재 상태에서 가능한 모든 선택지를 다 플레이해 보는 방법이 백 트래킹이다. 백 트래킹은 BFS, DFS처럼 기본적인 알고리즘 구조가 잡혀 있으니 잘 익혀 둘 필요가 있다.

 

접근

재귀 함수로 풀이해 보기로 했다. 1부터 n까지의 숫자 중 m개를 중복 없이 골라야 하므로 그 수들이 들어갈 배열(numbers)과 그 수를 이미 골랐는지 여부를 확인할 배열(isUsed)이 필요하다. 그리고 뽑은 수가 몇 번째 수인지는 변수 k를 두어 확인하였다.

 

알고리즘

1. 1부터 n까지의 수에 대해 for문을 돈다. 아직 i가 사용되지 않았다면 k번째 수는 i이다.

2. i를 사용했다고 배열에 표시한다.

3. 다음 수를 정하러 재귀 함수를 호출한다. 

4. 재귀 함수가 끝나면, k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i에 대한 선택 여부 배열을 초기화 해 준다. 

 

1. 함수 식

void func(int k) // k는 몇 번째로 뽑는 수인지

 

2. base condition

m개를 모두 뽑았으면, 즉 k==m이라면 뽑은 수들(numbers)을 모두 출력한다. 

 

3. 재귀 식

재귀 식은 위에 적은 알고리즘을 그대로 구현하면 된다.

 

코드

#include<iostream>
using namespace std;

int n, m;
int numbers[10];
int isUsed[10];

void Solve(int k)
{
    // k는 0부터 시작하므로 k == m이면 다 뽑고 다음 턴임.
    if (k == m)
    {
        for (int i = 0; i < m; i++)
            cout << numbers[i] << ' ';
        cout << '\n';
        return;
    }

    // 1부터 n까지의 숫자에 대해
    for (int i = 1; i <= n; i++)
    {
        // 아직 그 숫자가 사용되지 않았다면
        if (!isUsed[i])
        {
            numbers[k] = i;
            isUsed[i] = true;
            Solve(k + 1);
            isUsed[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    Solve(0);

    return 0;
}

 

참고 블로그

바킹독