BOJ 15650번 : N과 M(2)

<Solution>

이 전 문제에서 오름차순 조건이 추가되었다.

 

이런 저런 조건 필요 없이 이미 벡터에 들어있는 마지막 값보다 큰 값만 추가하면 자연히 오름차순이 만족된다.

 

또한, 처음 DFS 시작시 벡터의 마지막 값을 참조할 수 없으므로 그것 또한 예외처리를 해주면 된다.

 

<소스코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
void DFS(vector<int> v, vector<int> arr, vector<bool> chk, int cnt, int n, int m, int x) {
 
    if (!cnt || v[x] > arr.back()) { // 자신보다 큰 값만 추가함 & 처음 시작 예외처리
        chk[x] = 1; // 방문 체크
        arr.push_back(v[x]); // 값 넣어줌
        cnt++; // 갯수 계산
 
        if (cnt == m) { // 갯수만큼 뽑았을때
            for (int i = 0; i < m; i++)
                cout << arr[i] << ' ';
 
            cout << '\n'; // endl은 느려서 틀렸음....
        }
 
        for (int i = 0; i < n; i++) {
            if (!chk[i])  // 아직 방문하지 않은 것
                DFS(v, arr, chk, cnt, n, m, i);
        }
    }
    
}
 
void Solve(int n, int m) {
    vector<int> v(n); // 값 들어있음
    vector<bool> chk(n, 0); // 방문 체크
    vector<int> arr; // 출력할때 사용
    int cnt = 0; // 층수 계산
    for (int i = 0; i < n; i++)
        v[i] = i + 1;
 
    for (int i = 0; i < n; i++) 
        DFS(v, arr, chk, cnt, n, m, i); // 인덱스 i의 값이 시드값이 됨
 
}
 
int main() {
 
    int n, m;
    cin >> n >> m;
    Solve(n, m);
}

<문제>

www.acmicpc.net/problem/15650

15650번: N과 M (2)