백준 15649: N과 M (1)

문제 요약

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

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

문제 분류

• 백트래킹

문제 풀이

n까지의 수를 m번 DFS로 탐색하되, 모든 경우의 수를 출력하는 것이 목표이다.

즉, 노드를 끝까지 탐색했을 때 지금까지 지나온 모든 노드를 출력해야 하고, 이후 백트래킹하여 다시 탐색한다.

즉 현재의 진행상황을 저장할 ary[]를 만들어서 DFS로 탐색할때마다 i번째 레벨의 노드를 배열의 i인덱스에 저장하면 될 것이다. 또 중복은 허용하지 않으므로 visited[]로 탐색 여부를 확인하였다.

그리고 마지막까지 탐색했을경우 저장된 ary를 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

bool visited[9] = { false };
int ary[8], n, m;

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

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

후일담

DFS를, 정확하게는 재귀호출을 이용하여 해결하였지만, 알고리즘 분류에 DFS가 없었다. 이것은 이 문제가 그래프의 탐색이 아닌, 백트래킹의 개념이 확실하게 들어간 문제라고 보여진다.