백준 14600번 샤워실 바닥 깔기 (Small) C++

출처 : https://www.acmicpc.net/problem/14600

 

k의 범위가 1~2이기때문에 바닥의 크기는 2 혹은 4이다. 바닥의 크기가 크지 않기 때문에 백트래킹을 이용해서 모든 경우를  탐색하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[8][2] = { {0,1}, {0,-1} ,{1,1} ,{1,1} ,{0,-1} ,{0,1} ,{-1,-1} ,{-1,-1} };
int dCol[8][2] = { {1,1}, {1,1}, {0,1}, {0,-1}, {-1,-1}, {-1,-1}, {0,1}, {0,-1}, };
bool isPrinted = false;

void PrintBoard(const vector<vector<int>>& board) {
	for (auto a : board) {
		for (auto b : a) {
			cout << b << " ";
		}
		cout << "\n";
	}
}

void BT(int num, int len, int cnt, vector<vector<int>>& board) {
	if (isPrinted) return;
	if (cnt == len * len - 1) {
		if (!isPrinted) {
			PrintBoard(board);
			isPrinted = true;
		}
		return;
	}
	for (int k = 0; k < len * len; k++) {
		int row = k / len;
		int col = k % len;
		if (board[row][col] == 0) {
			for (int i = 0; i < 8; i++) {
				bool isPossible = true;
				for (int j = 0; j < 2; j++) {
					int nextRow = row + dRow[i][j];
					int nextCol = col + dCol[i][j];
					if (nextRow < 0 || nextRow >= len) {
						isPossible = false;
						continue;
					}
					if (nextCol < 0 || nextCol >= len) {
						isPossible = false;
						continue;
					}
					if (board[nextRow][nextCol] != 0) {
						isPossible = false;
						continue;
					}
				}
				if (isPossible) {
					board[row][col] = num;
					board[row + dRow[i][0]][col + dCol[i][0]] = num;
					board[row + dRow[i][1]][col + dCol[i][1]] = num;
					BT(num + 1, len, cnt + 3, board);
					board[row][col] = 0;
					board[row + dRow[i][0]][col + dCol[i][0]] = 0;
					board[row + dRow[i][1]][col + dCol[i][1]] = 0;
				}
			}
		}
	}
}

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

	int k;
	cin >> k;
	int len = pow(2, k);
	int x, y;
	cin >> x >> y;
	swap(x, y);
	x = len - x;
	y -= 1;
	vector<vector<int>> board(len, vector<int>(len, 0));
	board[x][y] = -1;
	BT(1, len, 0, board);
	if (!isPrinted) cout << -1;
};