[백준OJ] 14600번 샤워실 바닥 깔기 (Small)

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

14600번: 샤워실 바닥 깔기 (Small)

---

 

풀이

백트래킹을 이용해서 모든 경우를 탐색했다. 왜냐면 K의 값이 1<=K<=2이기 때문에, 모든경우를 탐색해도 시간이 남아돌기 때문이다.

빈곳을 만난다면, 8가지 타일중에 알맞는 타일을 하나 놓고 다음칸으로 넘어가며 재귀함수를 호출한다. 만약 끝까지 갔는데, 남아있는 타일이 있다면, 지금까지 해온걸 거슬러 올라오면서 다시 0으로 만들어준뒤 , 다음경우를 고려해서 실행해준다. 남아있는 타일이 있는지 없는지는, 2*2^K-1개에서, 해당 타일을 놓을 수 있으면 3개씩 빼주면서 재귀를 호출한다.

코드

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

int maze[5][5] = { 0 };
int k, x, y;
bool flag1 = false;
int tile[8][3][2] = {
	{{0,0},{1,0},{1,1}},
	{{0,0},{1,0},{1,-1}},
	{{0,0},{-1,0},{-1,1}},
	{{0,0},{-1,0},{-1,-1}},
	{{0,0},{0,1},{1,1}},
	{{0,0},{0,1},{-1,1}},
	{{0,0},{0,-1},{1,-1}},
	{{0,0},{0,-1},{-1,-1}},
};

bool isIn(int i, int j) {
	return 1 <= i && i <= k && 1 <= j && j <= k && maze[i][j] == 0;
}

void dfs(int num,int left) {
	if (left == 0) {
		for (int i = k; i >=1; i--) {
			for (int j = 1; j <= k; j++) {
				cout << maze[i][j] << " ";
			}
			cout << "\n";
		}
		flag1 = true;
		return;
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			if (maze[i][j] == 0) {
				for (int k = 0; k < 8; k++) {
					bool flag = true;
					for (int k1 = 0; k1 < 3; k1++) {
						int nx = i + tile[k][k1][0];
						int ny = j + tile[k][k1][1];

						if (!isIn(nx, ny)) {
							flag = false;
							break;
						}
					}
					if (flag) {
						for (int k1 = 0; k1 < 3; k1++) {
							int nx = i + tile[k][k1][0];
							int ny = j + tile[k][k1][1];
							maze[nx][ny] = num;
						}
						dfs(num + 1, left - 3);
						if (flag1) return;
						for (int k1 = 0; k1 < 3; k1++) {
							int nx = i + tile[k][k1][0];
							int ny = j + tile[k][k1][1];
							maze[nx][ny] = 0;
						}
					}
				}
				if (flag1) return;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> k;
	cin >> y >> x;
	maze[x][y] = -1;
	k = pow(2, k);
	dfs(1, k*k - 1);

	return 0;
}