15651 N과 M(3) (C++)

음... 일단 내가 생각한건 이거다... 기존의 백트래킹은, 그냥 한번 올라가거나, 뿌리 내려지기 전의 수부터 시작을 하지 않는다고 생각했다. 그래서 아얘 그냥 위부터 쭈우우우욱 올라가서 다시 출력하고 쭈우우욱 올라가서 출력하고..를 원했다.

 

그래서 그걸 표현한 코드가 있다.

 

근데 왜 작동 되는건지 모르겠다..

 

어떻게든 이해해보자.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int n,m;
int board[10];
int isused[10];

void func(int k) {
    if(k == m) {
		for(int i = 0; i < m; i++) {
			cout << board[i] << ' ';
		}
		cout << endl;
		return;
	}
	
	for(int i = 0; i < n; i++) {
		if(!isused[i]) {
			board[k] = i+1;
			isused[i+1] = 1;
			func(k+1);
			for(int i = 0 ; i < n; i++) {
				isused[i] = 0;
				isused[i+1] = 0;
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0);
}

 

자. 먼저 들어가서 수를 넣고, 방문했다라는걸 표현하는 isused의 배열을 True로 만들어준다.

그리고 재귀가 돌아가고, 만일 Base condition에 도달하면 출력을 한다.

그리고나서 이중 for문에 들어와서 모든 방문을 초기화 한다.

 

뭐 이런 로직인 것 같다! (이게 왜 됨..)