문제 : https://algospot.com/judge/problem/read/BOARDCOVER2
알고리즘 문제 해결 전략 p.423
[알고리즘 STEP. 1]
일단, 입력받은 블록을 4방향으로 돌려서(0도, 90도, 180도, 270도) 미리 저장해 둔다. 저장 할 때는 왼쪽 가장 위의 인덱스를 0,0으로 두고 나머지를 상대 위치로 변환해서 pair<int, int> 형태로 저장한다.(void generateRotations(vector<string> block))
vector<vector<pair<int,int>>> rotations; //roatations : block을 회전시켜 만든 4가지 블록을 pair<int, int>의 벡터로 저장
void generateRotations(vector<string> block){ //vector<string>&block 아니고 그냥 복사
rotations.clear();
rotations.resize(4);
FOR(rot, 4){
int xindex=-1, yindex=-1;
FOR(i, block.size()){
FOR(j, block[0].size()){
if(block[i][j]=='#'){
// 처음으로 만난 #이 블록의 가장 왼쪽 윗칸이다.
// 이를 (0,0)으로 해서 나머지 칸들의 상대 위치를 저장한다
if(xindex==-1) {
yindex = i;
xindex = j;
}
// 나머지 블록들의 상대위치를 계산(i-yindex, j-xindex)해서 pair로 만들어서 rotations[rot]에 넣는다.
// rotations[rot] : block을 rot번 회전한 블록의 칸들
rotations[rot].push_back(make_pair(i-yindex, j-xindex));
}
}
}
printVector(rotations[rot]);
//회전
block = rotate(block);
}
//중복제거
sort(rotations.begin(), rotations.end());
rotations.erase(unique(rotations.begin(), rotations.end()), rotations.end()); // ** unique함수!!
blocksize = rotations[0].size();
}
rotations는 현재 테스트케이스에서 주어진 블록을 회전시켜서 만들 수 있는 4개의 블록들을,
가장 왼쪽 위의 칸을 0,0으로 두고 나머지 칸의 상대 위치를 벡터로 저장한 것이다.
예를들어 첫번째 테스트케이스의 블록
###
#..
에 대한 rotations들은 다음과 같다.
| ### # . . |
## .# .# |
. .# ### |
# . # . ## |
| (0, 0) (0, 1) (0, 2) (1, 0) | (0, 0) (0, 1) (1, 1) (2, 1) | (0, 0) (1, -2) (1, -1) (1, 0) | (0, 0) (1, 0) (2, 0) (2, 1) |
- void generateRotations(vector<string> block){ //vector<string>&block 아니고 그냥 복사
generateRotations함수는 vector<string> block을 받아서 회전시킨다.
이 때 회전시킬 때 원래의 값이 바뀌지 않게 하기 위해서 reference가 아닌 value로 넘겨준다.
- rotations.resize(4);
미리 벡터의 사이즈를 정해주면 특정 원소에 바로 접근할 수 있다.
resize를 안해주었다면, 각 블록을 나타내는 벡터(vector<pair<int,int>> temp) 를 완성시킨 후에야 그 temp를 rotations에 push할 수 있다.( rotations.push_back(temp) )
하지만 여기서는 미리 resize를 해주었기 때문에 다음과 같이 rotations의 특정 인덱스에 직접 각 블록의 칸들을 push 할 수 있다.
rotations[rot].push_back(make_pair(i-yindex, j-xindex));
- rotations.erase(unique(rotations.begin(), rotations.end()), rotations.end()); // ** unique함수 사용법 찾아보기
벡터 안의 원소들의 중복을 제거하는 방법이다.
unique함수는 항상 정렬 후에 써야한다.
예를들어, 다음과 같은 벡터가 있을 때
int myints[] = {10,20,20,20,30,30,20,20,10};
std::vector<int> myvector (myints,myints+9);// 처음 벡터 : 10 20 20 20 30 30 20 20 10
정렬 후
sort(myvector.begin(), myvector.end()); //정렬 후 10 10 20 20 20 20 20 30 30
unique 함수 실행 후
(중복되는 원소들은 다 뒤로 미루고, 중복되는 원소가 시작되는 인덱스의 iterator를 반환한다)
vector<int>::iterator it;
it = unique (myvector.begin(), myvector.end()); // unique 실행 후 10 20 30 20 20 20 20 30 30
// unique는 앞에서 한번이라도 나왔던 원소는 뒤로 몰아넣고
cout << std::distance(myvector.begin(),it) << endl; // 3 반환
[알고리즘 STEP. 2]
// 해당 칸에 블록을 넣을 수 있는지 확인. 넣을 수 있다면 val값을 채워넣는다
bool set(int y, int x, const vector<pair<int, int>>& block, int val){
bool ret = true;
FOR(i, block.size()){
if(0<=y+block[i].first && y+block[i].first<r && 0<=x+block[i].second && x+block[i].second<c){
if(board[y+block[i].first][x+block[i].second]!=val) continue;
else{
ret = false;
break;
}
}
else{
ret = false;
break;
}
}
if(ret){
FOR(i, block.size()){
board[y+block[i].first][x+block[i].second]=val;
}
}
return ret;
}
void search(int placed){
int y = -1, x = -1;
//빈칸을 탐색해서 인덱스를 y,x에 저장
FOR(i, r){
FOR(j, c){
if(board[i][j] == 0){
y = i; x = j;
break;
}
}
if(y!=-1) break;
}
//빈칸이 없다면 지금까지의 최대값 잔환
if(y==-1){
best = max(best, placed);
return;
}
//빈칸이 있다면 4개의 블록을 한번씩 넣어봄
FOR(i, rotations.size()){
// roataions[i]블록을 넣을 수 있다면?
if(set(y, x, rotations[i], 1)) {
empty -= blocksize;
// 그 블록을 채운 상태로 재귀적으로 다시 실행
search(placed+1);
// 다 탐색했으면 다시 블록 제거
set(y, x, rotations[i], 0);
empty += blocksize;
}
}
// 칸을 채우지 않고 넘어가는 경우
board[y][x] = 1;
empty--;
search(placed);
// 탐색 후 다시 빈칸으로 만듬
board[y][x] = 0;
empty++;
}
[알고리즘 STEP. 3] 가지치기(pruning)
최대값을 구하는 게 문제이므로,
게임의 rule을 약간 줄여서 답을 과대평가한 (rule을 양보했을 때 답의 최대치) 값으로 pruning을 한다.
여기서는 (남은 빈칸의 수/블록 하나의 칸 수) 가 앞으로 채울 수 있는 블록의 수를 과대평가한 답이다.
설명하자면, 아마 block의 모양 때문에 대부분 이 값보다 작은 값이 나올 것이고,
운이좋게 남은 칸과 블록의 모양이 딱 들어맞는다면 최대 (남은 빈칸의 수/블록 하나의 칸 수)의 블록을 더 이용할 수 있게 된다.
이를 이용해서 search함수 첫 줄에 다음 코드를 넣어주면 pruning이 된다.
if(empty/blocksize+placed < best) return;
[최종코드]
//
// Created by HANLEEKYEUNG on 2017. 10. 19..
//
#include <vector>
#include <algorithm>
#include <iostream>
#include <string.h>
#define FOR(var, ed) for(int var = 0 ; var<ed; var++)
using namespace std;
int tc, r, c, br, bc, empty;
vector<string> iboard;
vector<string> block;
vector<vector<pair<int,int>>> rotations; //roatations : block을 회전시켜 만든 4가지 블록을 pair<int, int>의 벡터로 저장
int board[10][10];
int blocksize;
int best;
void getInput(){
iboard.clear();
memset(board, 0, sizeof(board));
block.clear();
string temp;
cin >>r>>c>>br>>bc;
empty = r*c;
FOR(i, r){
cin >> temp;
iboard.push_back(temp);
}
FOR(i, r){
FOR(j, c){
if(iboard[i][j] == '#'){
board[i][j]=1;
empty--;
}
}
}
FOR(i, br){
cin >> temp;
block.push_back(temp);
}
}
vector<string> rotate(vector<string> &arr){
vector<string> ret(arr[0].size(), string(arr.size(), ' '));
FOR(i, arr.size())
FOR(j, arr[0].size())
ret[j][arr.size()-i-1] = arr[i][j];
return ret;
}
// 해당 칸에 블록을 넣을 수 있는지 확인. 넣을 수 있다면 val값을 채워넣는다
bool set(int y, int x, const vector<pair<int, int>>& block, int val){
bool ret = true;
FOR(i, block.size()){
if(0<=y+block[i].first && y+block[i].first<r && 0<=x+block[i].second && x+block[i].second<c){
if(board[y+block[i].first][x+block[i].second]!=val) continue;
else{
ret = false;
break;
}
}
else{
ret = false;
break;
}
}
if(ret){
FOR(i, block.size()){
board[y+block[i].first][x+block[i].second]=val;
}
}
return ret;
}
void search(int placed){
if(empty/blocksize+placed < best) return;
int y = -1, x = -1;
//빈칸을 탐색해서 인덱스를 y,x에 저장
FOR(i, r){
FOR(j, c){
if(board[i][j] == 0){
y = i; x = j;
break;
}
}
if(y!=-1) break;
}
//빈칸이 없다면 지금까지의 최대값 잔환
if(y==-1){
best = max(best, placed);
return;
}
//빈칸이 있다면 4개의 블록을 한번씩 넣어봄
FOR(i, rotations.size()){
// roataions[i]블록을 넣을 수 있다면?
if(set(y, x, rotations[i], 1)) {
empty -= blocksize;
// 그 블록을 채운 상태로 재귀적으로 다시 실행
search(placed+1);
// 다 탐색했으면 다시 블록 제거
set(y, x, rotations[i], 0);
empty += blocksize;
}
}
// 칸을 채우지 않고 넘어가는 경우
board[y][x] = 1;
empty--;
search(placed);
// 탐색 후 다시 빈칸으로 만듬
board[y][x] = 0;
empty++;
}
void generateRotations(vector<string> block){ //&아니고 그냥 복사
//roatations : block을 회전시켜 만든 4가지 블록을 pair<int, int>의 벡터로 저장
rotations.clear();
rotations.resize(4);
FOR(rot, 4){
int xindex=-1, yindex=-1;
FOR(i, block.size()){
FOR(j, block[0].size()){
if(block[i][j]=='#'){
// 처음으로 만난 #이 블록의 가장 왼쪽 윗칸이다.
// 이를 (0,0)으로 해서 나머지 칸들의 상대 위치를 저장한다
if(xindex==-1) {
yindex = i;
xindex = j;
}
// 나머지 블록들의 상대위치를 계산(i-yindex, j-xindex)해서 pair로 만들어서 rotations[rot]에 넣는다.
// rotations[rot] : block을 rot번 회전한 블록의 칸들
rotations[rot].push_back(make_pair(i-yindex, j-xindex));
}
}
}
// printVector(rotations[rot]);
//회전
block = rotate(block);
}
//중복제거
sort(rotations.begin(), rotations.end());
rotations.erase(unique(rotations.begin(), rotations.end()), rotations.end()); // ** unique함수 사용법 찾아보기
blocksize = rotations[0].size();
}
int main(){
freopen("input.txt", "r", stdin);
cin >> tc;
while(tc--){
// cout << tc << endl;
best = 0;
getInput();
generateRotations(block);
search(0);
cout << best << endl;
}
}
'알고리즘' 카테고리의 다른 글
| algospot :: DARPA DARPA Grand Challenge (0) | 2017.10.22 |
|---|---|
| algospot :: ALLERGY 알러지가 심한 친구들 (0) | 2017.10.22 |
| algospot :: STRJOIN 문자열 합치기 (0) | 2017.10.17 |
| algospot :: LUNCHBOX 도시락 데우기 (0) | 2017.10.17 |
| algospot :: MATCHORDER 출전 순서 정하기 (0) | 2017.10.17 |
