백준 18808 스티커 붙이기 c++

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

18808번: 스티커 붙이기

좋좋소에서 볼법한 코드

푸는데 머리에서 김 나오는 줄 알았다. 지옥 같은 5 중반복문 함수분할하고 부등호 잘못된 것 디버깅하느라 죽을 맛이었다. 역시 x, y프린트 찍어보는 게 좌표사용문제에선 최고의 디버깅 방법인 듯하다. 

 

1.vector<Sticker> s에 들어있는 shape[0], col[0], row[0]에 스티커 정보 받아준다.

2. 스티커 돌려서 [1][2][3]다 넣어준다.

3. dfs 돌면서 board에 붙일 수 있으면 붙인다.

4. board에서 스티커 붙인 곳(1) 개수 세서 리턴

5. 무한 디버깅....

문제를 잘 봐야 한다 모든 경우를 다 탐색하는게 아니다. 스티커 하나를 붙일 수 있으면 돌리면 안 된다 붙일 수 없을 경우에만 돌리고 결국 못 붙여야 안 붙이는 경우가 가능하다.

시뮬레이션 문제는 특히 문제 잘못보면 시간 엄청 날릴 수 있다. 조심!

저 구조체에 dir별로 sticker shape, col, row 배열로 넣어놓아서 모양이 좀 별로지만 어쩔 수 없다... 내 금붕어 기억력으론 이렇게 안 하면 무조건 실수하기 때문..

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>
#include <climits> // int32max

using namespace	std;

struct Sticker {
	vector<vector<int> > shape[4]; // 돌려가면서 만들 모양
	int col[4];
	int row[4];
};
int col, row, sNum, sArea = 0; // sticker 개수
vector<Sticker> s;
vector<vector<int> > board;

vector<vector<int> > getTurnedBoard(vector<vector<int> > b) {
	int col = b[0].size(), row = b.size();

	vector<vector<int> > res(col, vector<int>(row, 0));
	for (int x = 0; x < col; x++) {
		for (int y = 0; y < row; y++) {
			res[x][y] = b[row - y - 1][x];
		}
	}
	return res;
}
// 11 12 13
// 21 22 23
// 31 32 33

// 31 21 11
// 32 22 12
// 33 23 13
void	turnSticker() { // 1 2 3 버전 돌려서 등록해줌
	for (int i = 0; i < s.size(); i++) {
		for (int j = 1; j < 4; j++) {
			s[i].shape[j] = getTurnedBoard(s[i].shape[j - 1]);
			s[i].col[j] = s[i].row[j - 1];
			s[i].row[j] = s[i].col[j - 1];
		}
	}
}

int getSArea() {
	int cnt = 0;
	for (int x = 0; x < col; x++)
		for (int y = 0; y < row; y++)
			if (board[x][y])
				cnt++;
	return cnt;
}

bool canPutSticker(int startX, int startY, int sIdx, int dir) {
	for (int x = 0; x < s[sIdx].col[dir]; x++) {
		for (int y = 0; y < s[sIdx].row[dir]; y++) {
			if (board[startX + x][startY + y] == 1 && s[sIdx].shape[dir][x][y] == 1)
				return false;
		}
	}
	return true;
}

void putSticker(int startX, int startY, int sIdx, int dir) {
	for (int x = 0; x < s[sIdx].col[dir]; x++) {
		for (int y = 0; y < s[sIdx].row[dir]; y++) {
			if (s[sIdx].shape[dir][x][y] == 1)
				board[startX + x][startY + y] = 1;
		}
	}
}

void	dfs(int sIdx) {
	if (sIdx == s.size()) {
		int curSArea = getSArea();
		sArea = max(sArea, curSArea);
		return ;
	}
	bool flag = true;
	for (int dir = 0; dir < 4; dir++) { // 4방향 다
		for (int startX = 0; startX <= col - s[sIdx].col[dir]; startX++) {
			for (int startY = 0; startY <= row - s[sIdx].row[dir]; startY++) {
				if (flag && canPutSticker(startX, startY, sIdx, dir)) {
					// cout << "x, y" << startX << "," << startY << endl;
					flag = false;
					vector<vector<int> > backup = board;
					putSticker(startX, startY, sIdx, dir);
					dfs(sIdx + 1);
					board = backup;
				}
			}
		}
	}
	if (flag)
		dfs(sIdx + 1); // 스티커 안붙히는 경우
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin >> col >> row >> sNum;
	for (int i = 0; i < col; i++) {
		vector<int> V;
		for (int j = 0; j < row; j++)
			V.push_back(0);
		board.push_back(V);
	}
	for (int i = 0; i < sNum; i++) {
		int sCol, sRow, arg;
		cin >> sCol >> sRow;
		Sticker input;
		for (int x = 0; x < sCol; x++) {
			vector<int> inputV;
			for (int y = 0; y < sRow; y++) {
				cin >> arg;
				inputV.push_back(arg);
			}
			input.shape[0].push_back(inputV);
		}
		input.col[0] = input.shape[0].size();
		input.row[0] = input.shape[0][0].size();
		s.push_back(input);
	}
	turnSticker();
	dfs(0);
	cout << sArea;
}