[백준/C,C++] 15650번: N과 M (2)

www.acmicpc.net/problem/15650

15650번: N과 M (2)

hackids.tistory.com/9

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

15649번과 유사한 백트래킹 입문 문제입니다. 로직은 비슷하나 하나의 조건이 더 추가되었는데, 해당 조건만 로직에 추가해주면 됩니다.

#include<iostream>
#include<vector>

using namespace std;

#define SIZE 9

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

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

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

    cin >> n >> m;

    dfs(1, 0);

    return 0;
}

파라미터로 정수하나를 더 받아 반복문 내 i의 초깃값으로 설정해주면 됩니다. 그리고 재귀 호출 시 받아온 값에서 1만큼 증가한 값을 다시 파라미터로 전달해주면 됩니다. 최초 반복문은 1~4, 이후 2~4, 3~4 이런 식으로 진행되기 때문에 이전에 선택된 노드보다 큰 값만을 고려해 다음 노드를 선택하게 됩니다.