개요

백준 17136: 색종이 붙이기

• 입력
  총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

• 출력
  모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

접근방식

1. paper 2차원 배열에 종이값을 받은 후, 색종이를 붙여야할 1인 칸들의 정보를
   좌표값을 저장하는 구조체 oneinfo형의 vector에 넣어준다.

int paper[11][11];

struct oneInfo {
	int height;
	int width;
};
vector<oneInfo> ones;

2. backtracking함수는 vector<oneInfo> 의 iterator을 인자로 받는다.

void Bactracking(vector<oneInfo>::iterator oneOffset)

3. vector<oneInfo>의 iterator가 벡터의 end()에 도달하면,
   전체 다 순회했으므로 didFinished 변수를 false로 바꿔주고
   최소값을 찾기위한 전역변수 minAns값을 갱신해준다.

	if (oneOffset == ones.end()) {
		didFinished = true;
		minAns = minAns < HowMuchPaperUsed() ? minAns : HowMuchPaperUsed();
		return;
	}

4. 다음 iterator가 이미 덮힌 부분일때는 패스하고 다음 단계의 백트래킹으로 넘어간다

	//만약 다음 1의 자리가 색종이 덮여있다면 다음 1의자리로 패스
	if (covered[oneOffset->height][oneOffset->width]) {
		Bactracking(oneOffset + 1);
		//1의 자리가 덮여있다면 밑의 과정 처리 안해도되므로 백트래킹 끝나고 바로 return
		return;
	}

5. 그 후, 색종이를 iterator가 가리키는 1의 칸에 5x5사이즈부터 1x1사이즈까지 차례대로 넣으며 10x10종이의 범위를 넘어가거나, 0을 종이로 덮게되는지 체크한다.

//0이 색종이로 커버가 된다면 continue , i값 더했을때 범위벗어나면 continue해줘야됨(범위도 더한값이 10까지 허용해줘야 끝값 체크 가능)
		if ((oneOffset->height + i > 10 || oneOffset->width + i > 10) || checkIfZeroCovered(i, oneOffset->height, oneOffset->width))
			continue;

6. 범위를 안 벗어나고, 0을 안 덮는다면 해당 종이에 해당하는 paperamount값을 1감소시키고
   갯수가 음수가되면 다시 false로 바꿔준 후, 갯수를 다시 증가시켜서 continue한다.

		//갯수가 음수가 나온다면 이번 재귀에서 바꾼 covered값들 초기화 
			if (paperAmount[i - 1] < 0) {
				returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
				paperAmount[i - 1] ++;
				continue;
			}

7. 그후 paperAmount갯수가 깎인 정도로 몇개의 종이를 사용했는지 보고,
   minAns값보다 많이 사용했다면 바로 continue키워드로 가지치기를 했다.

	// 종이사용한 양이 최소 사용갯수보다 많다면 continue
			//처음엔 minAns를 큰값으로 잡고 통과하게 해 맨처음 통과되었을때 값으로 갱신하면서 가지치기
			if (HowMuchPaperUsed() >= minAns) {
				returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
				paperAmount[i - 1]++;
				continue;
			}

8. 그 후 가지치가 끝난 후 다음 백트래킹을 호출한다.

			Bactracking(oneOffset + 1);
			//백트래킹끝나고 초기화
			returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
			paperAmount[i - 1]++;
		}

전체 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int paper[11][11];

//좌표값 저장 구조체
struct oneInfo {
	int height;
	int width;
};

//1칸들 접근 용이하게 하는 벡터
vector<oneInfo> ones;
//모든값을 다 순회하였는지 체크하는 bool형 변수
bool didFinished = false;
int minAns = 100;
bool covered[10][10];
int paperAmount[5] = { 5,5,5,5,5 };

void Input() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> paper[i][j];
			if (paper[i][j] == 1) ones.push_back({ i,j });
		}
	}
}

//그냥 단순히 h,w에서 num만큼 다 false로 해버리면 예를들어 num이 5일때 1,2가 0일때 방금 조사안한값들도 다 false로 바꿔놓음
void returnCoveredToFalse(int num, int height, int width) {
	for (int i = height; i < num + height; i++) {
		for (int j = width; j < num + width; j++) {
			if (covered[i][j])
				covered[i][j] = false;
			else
				continue;
		}
	}
}

/// <summary>
/// height,width좌표에 numxnum 크기의 종이 붙였을 때 0이 덮히는지 체크하는 함수
/// </summary>
/// <param name="종이 한 변사이즈(num)"></param>
/// <param name="좌표 행(height)"></param>
/// <param name="좌표 열(width)"></param>
/// <returns></returns>
bool checkIfZeroCovered(int num, int height, int width) {
	for (int i = height; i < height + num; i++) {
		for (int j = width; j < width + num; j++) {
			//0을 만나면 true리턴
			//covered가 false일때만 true로 변경해야함 아니면 line92 안에서 백트래킹할때 그안에 이미 방문했음에도 다시 변경해버림
			if (paper[i][j] == 0|| covered[i][j]==true) {
				return true;
			}
			//paper가 1이라면 continue
			else
				continue;
		}
	}
	//이렇게 한번 더써주는 이유는 covered배열 false로 바꿔주는 함수가 싹다 false로 바꿔버려서
	//이전단계에서 true로 바꿔둔것도 다 바꿔버림
	for (int i = height; i < height + num; i++) {
		for (int j = width; j < width + num; j++) {
			covered[i][j] = true;
		}
	}
	return false;
}

int HowMuchPaperUsed() {
	int ansNum = 0;
	for (int i = 0; i < 5; i++) {
		ansNum += 5 - paperAmount[i];
	}
	return ansNum;
}

void Bactracking(vector<oneInfo>::iterator oneOffset) {
	if (oneOffset == ones.end()) {
		didFinished = true;
		minAns = minAns < HowMuchPaperUsed() ? minAns : HowMuchPaperUsed();
		return;
	}
	//만약 다음 1의 자리가 색종이 덮여있다면 다음 1의자리로 패스
	if (covered[oneOffset->height][oneOffset->width]) {
		Bactracking(oneOffset + 1);
		//1의 자리가 덮여있다면 밑의 과정 처리 안해도되므로 백트래킹 끝나고 바로 return
		return;
	}
	for (int i = 5; i > 0; i--) {
		//0이 색종이로 커버가 된다면 continue , i값 더했을때 범위벗어나면 continue해줘야됨(범위도 더한값이 10까지 허용해줘야 끝값 체크 가능)
		if ((oneOffset->height + i > 10 || oneOffset->width + i > 10) || checkIfZeroCovered(i, oneOffset->height, oneOffset->width))
			continue;
		//0이 안된다면 이미 해당 구역의 1들은 다 covered가 true 체크되었을 것.
		else {
			//갯수 -1 해줌
			paperAmount[i - 1]--;
			//갯수가 음수가 나온다면 이번 재귀에서 바꾼 covered값들 초기화 
			if (paperAmount[i - 1] < 0) {
				returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
				paperAmount[i - 1] ++;
				continue;
			}
			// 종이사용한 양이 최소 사용갯수보다 많다면 continue
			//처음엔 minAns를 큰값으로 잡고 통과하게 해 맨처음 통과되었을때 값으로 갱신하면서 가지치기
			if (HowMuchPaperUsed() >= minAns) {
				returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
				paperAmount[i - 1]++;
				continue;
			}
			Bactracking(oneOffset + 1);
			//백트래킹끝나고 초기화
			returnCoveredToFalse(i, oneOffset->height, oneOffset->width);
			paperAmount[i - 1]++;
		}
	}
}

void Solution() {
	Bactracking(ones.begin());
	//모두 탐색 못했다면 -1 출력
	if (!didFinished) {
		cout << -1;
		return;
	}
	cout << minAns;
}

int main() {
	Input();
	Solution();
}

문풀후생

일단 굉장히 많은부분에서 백트래킹에 대해 부족한 점을 느낀 문제였다.

일단 처음에 구현한 방식은 색종이를 5x5부터 큰 종이부터 덮는 방식이였는데
이런 그리디 방식으로 구현해버리면 큰값부터 들어가고 나머지를 1x1, 2x2로 채우는 방식이
최솟값이 아닌데도 불구하고 각 장의 갯수를 5장이내로 사용할 수 있다면 답으로 출력해버렸다.

또한, checkIfZeroCovered 함수에서도 covered[i][j]=true로 설정하는 부분을
또 쓰기 싫어서 매번 체크하고 입력값이 0이 아닐때 바로 covered[i][j]를 true로 대입하다보니, 비교할때마다 변경해버리는 문제가 있었다.

또한 checkIfZeroCovered함수에서 covered[i][j]가 true인지 체크하는 과정이 있어야,
이미 전 단계에서 방문한 부분이 패스가 되는데 그부분이없이 바로
paper[i][j]=0만 비교하니
이전 단계에서 covered값이 true로 바뀌어서 안 건드려야하는데도 불구하고
for(int i=5;i>0;i++) 부분의 반복문에서 해당 범위전체를 다시 true로 바꿔버려서 건드리게되었었다,