[수학] (조합론) backtracking으로 2차원 배열의 조합 탐색하기

[백준] 14502번 연구소를 풀다가 화딱지가 나서 겨우겨우 구현했다. 이게 과연 쓸 일이 있을까 해서 그냥 남겨둔다. 백트래킹으로 1차원 배열의 조합은 구현해봤어도 2차원 배열의 조합은 처음 해본다. 생각보다 생각해내기 어려웠다.... 직접 손으로 써보면서 겨우 찾아냈다..

 

y좌표가 증가하는 순으로 x좌표가 무조건 0부터n-1까지가 아니라

다음 탐색에서 y랑 같을 때만 x이고 그 다음부터는 0부터 n-1까지이다.

 

x부터가 아니라 바로 x+1부터로 하면 되지 않냐? 하는 의문이 들지만 해보면 처음 채울 때에 첫째칸이 안채워진다. 따라서 x부터 하는게 맞다.

 

#include<iostream>

using namespace std;
int map[4][4];
int cnt;

void print() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) cout << map[i][j] << " ";
		cout << "\n";
	}
}

void backtracking(int cur,int y, int x) {
	if (cur == 3) {
		cout << ++cnt << "회: \n";
		print();
		return;
	}

	for (int i = y; i < 4; ++i) {
		//입력받은 y에 대하여 처음에만(i == y인 경우) x부터 시작, 나머지는 0부터 시작
		int j =  i == y ? x : 0;
		for (; j < 4; j++) {
			if (!map[i][j]) {
				map[i][j] = 1;
				backtracking(cur + 1, i, j);
				map[i][j] = 0;
			}
		}
	}
}

int main(void) {
	backtracking(0, 0, 0);
}