[15649] N과 M (1)

---

백트래킹 문제이다

오랜만에 다시 공부하니까 머리 터질 것 같다

dfs 방식으로 문제를 풀 것이다

 

1. 중복이 되지 않으면서

2. 순열(순서를 따짐)

 

이어야 한다

 

 

그래프를 그려보면

일단 중복인 값들은 들어가면 안되겠죠? 그렇게 탐색한 과정이 위와 같다

 

그렇다면 중복인 값을 걸러주기 위해 visited 배열을 만든다

 

말로 설명하기 어려우니 직접 돌아가는 과정을 적어보았다

N=4, M=2인 경우이다

마지막에 visited[i]=false는 print 후 원상복구 시키는 역할을 한다

visited[i]=true는 dfs로 더 깊숙히 들어갈 때 중복되는 숫자를 방지하기 위함이다

 

 

그렇게 완성된 코드는 아래와 같다(틀을 외우도록 하자)

#include <iostream>
using namespace std;

int N, M;
int A[8];
bool visited[9];

void f(int x) {
	if (x == M) {
		for (int i = 0; i < M; i++) {
			printf("%d ", A[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) { // 방문하지 않았다면
			visited[i] = true;
			A[x] = i;
			f(x + 1);
			visited[i] = false; // 다시 바꿔서 다른 곳으로

		}
	}
}	

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	f(0);

}