[C++/백준] 17136 색종이 붙이기

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

 

 

[풀이 방법]

백트래킹

재귀를 사용해서 색종이가 있는 칸이면 5~1까지 색종이를 모두 붙이고 체크한 후 다음으로 넘어간다. 

#include<iostream>
#include<tuple>
#include<queue>
#include<vector>
#include<algorithm>

int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

int Board[10][10];

int ans = 2e9;
using namespace std;


void input() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int i = 0;i < 10;i++)
		for (int j = 0; j < 10; j++)
			cin >> Board[i][j];
}

bool available(int _y, int _x, int w) {
	for (int y = _y; y < _y + w;y++) {
		for (int x = _x; x < _x + w;x++) {
			if (Board[y][x] == 0)
				return false;
		}
	}
	return true;
}

void try_stick(int _y, int _x, int w,int num) {
	for (int y = _y; y < _y + w; y++) {
		for (int x = _x; x < _x + w; x++) {
			Board[y][x] = num;
		}
	}
}

bool check_empty() {
	for (int y = 0;y < 10;y++) {
		for (int x = 0; x < 10; x++) {
			if (Board[y][x])
				return false;
		}
	}
	return true;
}

void DFS(vector<int> &paper, int sum, int py) {
	if (ans <= sum)
		return;

	if (check_empty()) {
		ans = min(ans, sum);
		return;
	}


	for (int y = py; y < 10; y++) {
		for (int x = 0; x < 10; x++) {
			if (Board[y][x] == 1) {
				for (int w = 5;w > 0;w--) {
					if (paper[w] >= 5 || x + w > 10 || y + w > 10) continue;
					if (!available(y, x, w))
						continue;
					paper[w] += 1;
					try_stick(y, x, w, 0);
					DFS(paper, sum + 1, y);
					try_stick(y, x, w, 1);
					paper[w] -= 1;
				}
				return; // 어차피 색종이를 다 대입 시킨 후로 더 이상 반복문을 돌 필요가 없다.
			}
		}
	}

	return;
}



int main() {
	input();
	vector<int> paper(6);
	fill(paper.begin(), paper.end(), 0);
	DFS(paper, 0, 0);
	if (ans == 2e9)
		ans = -1;
	cout << ans;

	return 0;
}

 

 

[회고]

백트래킹을 오랜만에 해서 사실 잘 기억이 안났다.. 좀 더 많이 풀어야겠음. 

 

처음에 2차원 배열 copy를 사용했는데 이 방법은 상당히 오랜 시간이 걸린다. -> 다른 사람들을 좀 참고하니까 저런식으로 0을 칠하고 1을 칠하고 하는 방법을 사용했음. 

 

배열  call by를 오랜만에 해서 잘 기억이 안났는데 파라미터로 int board[10][10] 받고 그냥 board 넘겨주면 
함수에 의한 호출로 전달된다. 

 

copy도 간만에 썼는데 copy(복사할 첫 주소, 복사할 마지막 주소, 옮겨담을 변수) 이렇게 하면 됨. 아휴..ㅠㅠ

 

또 다 짜놨더니 시간초과 시간초과 되어서 포스팅 참고를 좀 했는데 

 

1) 색종이 붙이는 범위 확인 안함 x+w>10|| y+w>10 이걸 해줘야 한다. 

2) 한 부분을 다 보고나면 다음으로 넘어가면 안된다 -> 무조건 붙여야 하기 때문에 그 칸에서 다 확인해줬으면 그냥 return 해야 시간이 된다. 

 

접근 -> 모든 경우를 확인해야한다. -> 완전 탐색 / 브루트포스 (DFS)