[BOJ/백준/C++] 15649번

15649번: N과 M (1)

---

반응형

📌 접근 방법

• 백트래킹 원리를 사용했다

✔️ 백트래킹 

• 가능한 모든 해를 조사하면서 최적의 해를 찾는 기법
• 재귀적인 방법으로 구현
• 해를 찾기 위해 후보해를 조사하고, 조건을 만족하지 않으면 이전 상태로 돌아가 다른 후보를 조사하는 과정을 반복함

 

✔️ 깊이 우선 탐색 (Depth-First Search, DFS) 

• 그래프의 모든 정점을 탐색하는 기법
• 스택(Stack) 또는 재귀 함수를 통해 구현가능

1. 시작 정점을 선택하고 해당 정점을 방문했음을 표시함
2. 선택한 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점을 하나 선택함
3. 선택한 정점을 스택에 넣고 방문했음을 표시
4. 선택한 정점으로 이동하고 해당 정점을 방문했음을 표시
5. 선택한 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점을 하나 선택함
6. 위 과정을 계속 반복
7. 만약 더 이상 방문하지 않은 정점이 없다면 스택에서 하나의 정점을 꺼내고, 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 선택함
8. 스택이 빌 때까지 반복

✅  Pass Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
#include<unordered_set>
#include <stack>
#include<queue>
#include<deque>

using namespace std;

int N,M;
int *arr;
vector<int> v;
bool *visited;
void dfs(int k){
    if(k==M){
        for(int i=0; i<M; i++){
            cout<<v[i]<<' ';
        }
        cout<<'\n';
        return ;
    }
    for(int i=0; i<N; i++){
        if(visited[i]){
            continue;
        }
        visited[i]=true;
        v.push_back(arr[i]);
        dfs(k+1);
        v.pop_back();
        visited[i]=false;
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>M;

    visited = new bool[N];
    arr = new int[N];

    for(int i=0; i<N; i++){
        arr[i]=i+1;
        visited[i] = false;
    }
    dfs(0);
    return 0;
}