[BOARDCOVER2] 문제 😭😊😒😂😄
H×W 크기의 게임판과 한 가지 모양의 블록이 여러 개 있습니다. 게임판에 가능한 많은 블록을 올려놓고 싶은데, 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있으며 이 중에서 흰 칸에만 블록을 올려놓을 수 있습니다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 격자에 어긋나게 덮거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다.
위 그림은 예제 게임판과 L 자 모양의 블록으로 이 게임판을 덮는 방법을 보여줍니다. 게임판에는 15개의 흰 칸이 있고, 한 블록은 네 칸을 차지하기 때문에 그림과 같이 최대 세 개의 블록을 올려놓을 수 있지요. 게임판과 블록의 모양이 주어질 때 최대 몇 개의 블록을 올려놓을 수 있는지 판단하는 프로그램을 작성하세요.
[풀이]
이전 BOARDCOVER 와 비슷하면서도 좀더 어려운 문제였던것 같습니다.
먼저 input으로 받아온 block을 4방향으로 가능한 block 을 왼쪽위의 블록을 기준으로 ‘vector<vector<pair<int,int> > >’ 에 저장하는 전처리과정을 거칩니다.
다음으로 이전 BOARDCOVER에서 했던 완전탐색으로 문제를 해결하는데 이 문제는 가지치기를 해주지않으면 시간내에 수행하지 못합니다.
그리하여 마지막으로 현재 남은 빈공간을 blocksize로 나눈 것과 현재 둔 block의 개수의 합이 best(결과)보다 좋지않으면 그이상 수행하지않고 돌아갑니다.
이전 BOARDCOVER와 다른점은 전처리과정, 가지치기과정입니다. 나머지는 동일하게 완전탐색으로 해결하였습니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T (T≤100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 게임판의 크기 H, W (1≤H, W≤10), 그리고 블록의 모양을 나타내는 격자의 크기 R, C (1≤R, C≤10)가 주어집니다. 다음 H줄에는 각각 W 글자의 문자열로 게임판의 정보가 주어집니다. 문자열의 각 글자는 게임판의 한 칸을 나타내며, #은 검은 칸, 마침표는 흰 칸을 의미합니다. 다음 R줄에는 각 C 글자의 문자열로 블록의 모양이 주어집니다. 이 문자열에서 #은 블록의 일부, 마침표는 빈 칸을 나타냅니다.
각 게임판에는 최대 50개의 흰 칸이 있으며, 각 블록은 3개 이상 10개 이하의 칸들로 구성됩니다. 변을 맞대고 있는 두 변이 서로 연결되어 있다고 할 때, 블록을 구성하는 모든 칸들은 서로 직접적 혹은 간접적으로 연결되어 있습니다.
출력
각 테스트 케이스마다 게임판에 놓을 수 있는 최대의 블록 수를 출력합니다.
입력 예제
2
4 7 2 3
##.##..
#......
#....##
#..####
###
#..
5 10 3 3
..........
..........
..........
..........
..........
.#.
###
..#
출력 예제
3
8
전체 코드는 다음과 같습니다.
//
// BOARDCOVER2.cpp
// AALGGO
//
// Created by inhyeok on 2021/10/31.
//
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
ifstream fin("BOARDCOVER2.txt");
int BoardHeight;
int BoardWidth;
int BlockHeight;
int BlockWidth;
vector<string> Board;
vector<vector<pair<int ,int> > > rotations;
int blockSize;
int cover[10][10];
int best;
vector<string> rotate(const vector<string> &block){
vector<string> ret(block[0].size(), string(block.size(),' '));
for(int i=0; i< block.size(); i++){
for(int j=0; j < block[0].size(); j++){
ret[j][block.size()-i-1] = block[i][j];
}
}
return ret;
}
//-----
void Block_preprocesing(vector<string> block){
rotations.clear();
rotations.resize(4);
for(int rotation = 0; rotation<4; rotation++){
int X = -1, Y = -1;
for(int i=0 ; i<block.size(); i++){
for(int j=0; j<block[i].size(); j++){
if(block[i][j]=='#'){
if(Y == -1){
Y = i;
X = j;
}
rotations[rotation].push_back(make_pair(i-Y, j-X));
}
}
}
block = rotate(block);
}
sort(rotations.begin(), rotations.end());
rotations.erase(unique(rotations.begin(), rotations.end()),rotations.end());
blockSize = rotations[0].size();
}
// todo
// delta
bool set(int y, int x, const vector<pair<int,int>> &block, int delta){
bool result = true;
for(int i=0; i< block.size(); i++){
if(y+block[i].first >=0 && y+block[i].first<BoardHeight && x+block[i].second >=0 && x+block[i].second < BoardWidth){
cover[y+block[i].first][x+block[i].second] += delta;
result = result && (cover[y+block[i].first][x+block[i].second] == 1);
}
else{
result = false;
}
}
return result;
}
bool prune(int placed){
int cnt = 0;
for(int i=0; i<BoardHeight; i++){
for(int j=0; j<BoardWidth; j++){
cnt += (cover[i][j]) ? 0:1;
}
}
if((cnt/blockSize) + placed <= best)
return true;
else{
return false;
}
}
void search(int placed){
//가지치기
if(prune(placed)) return;
// 놓여 지지않은 가장 왼쪽 위 칸을 찾는다.
int Y = -1, X = -1;
for(int i=0; i<BoardHeight; i++){
for(int j=0; j<BoardWidth ; j++){
if(cover[i][j] == 0){
Y = i;
X = j;
break;
}
}
if(Y != -1) break;
}
if(Y == -1) {
best = max(best, placed);
return;
}
//cout << placed << endl;
// 이칸을 덮는다.
for(int i=0; i<rotations.size(); i++){
if(set(Y,X,rotations[i], 1))
search(placed+1);
set(Y,X,rotations[i], -1);
}
// 이칸을 막아둔다.
cover[Y][X] = 1;
search(placed);
cover[Y][X] = 0;
}
int solve(){
best = 0;
for(int i=0; i< BoardHeight; i++){
for(int j=0; j<BoardWidth; j++){
cover[i][j] = ( Board[i][j] == '#'? 1 : 0 );
}
}
search(0);
return best;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
Board.clear();
fin >> BoardHeight >> BoardWidth >> BlockHeight >> BlockWidth;
for(int i=0; i<BoardHeight; i++){
string board;
fin >> board;
Board.push_back(board);
}
vector<string> Block;
for(int i=0; i<BlockHeight; i++){
string block;
fin >> block;
Block.push_back(block);
}
Block_preprocesing(Block);
cout << solve() << endl;
}
return 0;
}
Comments