BOJ 15649번 : N과 M(1)

기본적인 백트래킹 문제이다.

 

c++의 endl 때문에 한번 시간초과가 나긴 했다.....

 

<Solution>

백트래킹의 경우 트리로 생각하면 간단하게 해결 할 수 있다.

 

(4,2)가 입력일때, 루트노드가 1이라면 자식노드는 1을 제외한 2,3,4 가 되고, 트리의 계층이 2층 이므로 모두 탐색을 완료한 것이다.

 

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) {
 
    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/15649

15649번: N과 M (1)