[백준 18808번 C/C++] 스티커 붙이기

 

[백준 18808번 C/C++] 스티커 붙이기

 

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

18808번: 스티커 붙이기

---

 

해결전략

 

구현 브루스포스 Brute Force

 

---

 

정답 코드

 

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

int n, m, k; // 노트북의 크기(n*m)와 스티커의 개수(k)
int r, c; // 각 스티커의 크기(r*c)
vector<vector<int>> v; // 노트북 격자
vector<vector<int>> sticker; // 각 스티커를 저장하기 위한 격자
int stickerCnt; // 스티커에 포함된 1의 개수
int answer; // 정답을 저장하기 위한 변수

// 스티커를 90도 회전시키는 함수
void Rotate()
{
	// 회전된 스티커를 임시로 저장할 격자 temp를 생성
	vector<vector<int>> temp(c, vector<int>(r));
	for (int y = 0; y < r; y++)
		for (int x = 0; x < c; x++)
			temp[x][r - 1 - y] = sticker[y][x]; // 시계방향으로 90도 회전

	sticker = temp; // 회전된 스티커를 저장
	swap(r, c);  // 스티커의 행과 열을 교환
}

// 스티커를 붙일 수 있는지 확인하고 붙이는 함수
bool checkNpaste(const vector<vector<int>>& sti)
{
	// 가능한 모든 위치에 대해
	for (int i = 0; i <= n - r; i++) {
		for (int j = 0; j <= m - c; j++) 
		{
			int cnt = 0;
			bool isPossible = true;
			vector<pair<int, int>> temp;
			// 스티커를 붙일 수 있는지 확인
			for (int y = i; y < i + r; y++) {
				for (int x = j; x < j + c; x++) {
					if (sti[y - i][x - j] == 1 && v[y][x] == 1) {
						isPossible = false;
						break;
					}
					else if (sti[y - i][x - j] == 1 && v[y][x] == 0) {
						temp.push_back({ y, x });
						cnt++;
					}
				}
				if (false == isPossible) break;
			}
			// 스티커를 붙일 수 있다면 붙이기
			if (cnt == stickerCnt)
			{
				for (int i = 0; i < temp.size(); i++)
					v[temp[i].first][temp[i].second] = 1;

				return true;
			}
			temp.clear();
		}
	}

	return false; // 스티커를 붙일 수 없다면 false 반환
}

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

	// 입력 받기
	cin >> n >> m >> k;
	v.resize(n, vector<int>(m));

	while (k--){
		cin >> r >> c;
		sticker.resize(r, vector<int>(c));
		stickerCnt = 0;
		// 스티커 정보 입력 받기
		for (int y = 0; y < r; y++) {
			for (int x = 0; x < c; x++) {
				cin >> sticker[y][x];
				if (sticker[y][x] == 1) stickerCnt++;
			}
		}

		int rotateCnt = 0;
		while (true) {
			// 스티커를 붙일 수 있으면 붙이고 다음 스티커로 넘어가기
			if (checkNpaste(sticker)) {
				answer += stickerCnt;
				break;
			}
			else {
				Rotate(); // 스티커를 붙일 수 없으면 회전

				rotateCnt++;
			}

			if (rotateCnt == 4) break; // 4번 회전했는데도 스티커를 못 붙이면 다음 스티커로 넘어가기
		}
		sticker.clear();
	}

	cout << answer << "\n";

	return 0;
}

 

 

---