알고리즘/BFS, DFS
[C++] 백준 15649번 N과 M (1)
키베이루
2022. 6. 19. 00:49
1) 문제설명
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
2) 아이디어
DFS를 사용하여 백트래킹으로 구현한다.
3) 코드
#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
int visited[11];
int arr[11];
int m, n;
void dfs(int k) {
if (k == m) {
for (int i = 0; i < m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++) { // 1 ~ 4
if (visited[i] == 0) {
arr[k] = i; // arr[0] = 1
visited[i] = 1;
dfs(k + 1);
visited[i] = 0;
}
}
}
int main() {
cin >> n >> m; // 4 2
dfs(0);
}