백준

[c++/백준] 10974 모든 순열

돈 많은 백수가 되고싶다 2023. 5. 11. 18:31

https://www.acmicpc.net/problem/10974

 

10974번: 모든 순열

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

www.acmicpc.net

전형적인 백트래킹 문제이다.

N과 M 문제 풀어봤으면 걍 눈 감고도 풀기 가능하다.

https://hello-world-cpp.tistory.com/2

 

[백준/c++] 15649 N과 M(1)

https://www.acmicpc.net/problem/15649 전형적인 백트래킹 문제,, DFS를 참고해서 풀면 된다. 중복도 허용하기 때문에 백트래킹계의 순열이라고 볼 수 있다. DFS의 재귀를 이용하여 풀었다. 자세한 설명은 코

hello-world-cpp.tistory.com

여기 더 자세하게 코드 설명 해놨다. 너무 똑같아서 코드 설명 따로 할게 없다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[10];
bool isVisited[10] = { false };
int n;

void backTracking(int depth) {
	if (depth == n) {
		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}
		cout << '\n';
	}
	for (int i = 1; i <= n; i++) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			arr[depth] = i;
			backTracking(depth + 1);
			isVisited[i] = false;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	backTracking(0);
}

그치만 어쩌면 나는 문제 답을 외워버렸을지도..?