[백준/C,C++] 15649번: N과 M (1)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

백트래킹 입문 문제입니다. 예제 입력을 예로 들면 4 2가 입력되었을 때, 1부터 4까지 자연수 중에서 중복 없이 2개를 고른 모든 수열을 나열해야 합니다.

흔히 말하는 트리 탐색 알고리즘과 상당히 유사한 모양인데, 이중 조건에 맞지 않는 노드를 배제하고 탐색한다는 점이 백트래킹의 특징입니다. 해당 트리에서 1 이후에는 중복되는 1이 올 수 없으니 2, 3, 4가 이후 노드로 선택될 수 있습니다.

#include<iostream>

using namespace std;

#define SIZE 9

int n, m;
int res[SIZE];
bool visited[SIZE];

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

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

    cin >> n >> m;

    dfs(0);

    return 0;
}

visited로 이름 붙인 불리언 배열을 통해 노드의 상태를 반영해줄 수 있습니다. 처음 1이 선택되는 과정에서 visited[1]은 true로 값이 바뀌고 결괏값 배열인 res에 1이 저장됩니다. 그리고 총 선택된 노드의 개수를 파라미터로 dfs 함수를 재귀 호출합니다. 다음 실행된 함수에서는 visited[1] 값이 true(즉, 1은 이미 선택된 노드)이므로 1을 건너뛰고 2를 다음 노드로 선택하게 됩니다. res에는 1, 2가 저장되고 dfs(2)가 실행되는데 파라미터로 전달받은 2는 선택해야 하는 수열의 길이인 m과 같으므로 res를 출력하고 되돌아갑니다.