[백트랙킹]백준18809번 gaaaaaaaaaarden
업데이트:
백준18809 gaaaaaaaaaarden
백트랙킹과 bfs를 이용해 해결한 문제다. 깔끔하게 해결되지는 않았고 궁금한 점도 남았지만..
구현을 연습해볼 수 있는 문제이기 때문에 문제 해결 방법이 잘 생각나지 않는다면 알고리즘만 이해한 후 구현을 직접 하는 것을 추천하는 문제이다.
우선 전체적인 알고리즘은 다음과 같다.
- 입력으로 들어오는 땅 중에서 노란색 땅은 따로 배열에 담는다.
- 초록색과 빨간색 배양액에 각각 숫자 변수를 할당한다.
- 예를 들어 초록색 배양액은 3, 빨간색 배양액은 4로 할당하였다.
- 배양액을 담을 배열을 만들고, 각 배양액들을 배열에 담는다.
- 전체 노란 땅들 중에 배양액을 배치할 땅을 고른다.
- 전체 노란 땅들 중에 배양액의 수 만큼 땅을 선택한다.
-
고른 땅에 배치할 배양액의 순열을 구한다.
예) RGGR, GRGR, RRGG 등…
선택한 땅에 선택한 배양액의 순열을 가지고 bfs를 진행한다.
땅을 고르고
배양액 순열을 구하고 하나를 선택하고
bfs를 진행한다.
BFS를 진행할 때는 시간에 주의해야 한다.
while(!q.empty()){
tuple<int,int,int> cur = q.front();
q.pop();
if(tmp[get<0>(cur)][get<1>(cur)].first==-1) continue;
if(1){
for(int i=0;i<4;i++){
int tmp_y = get<0>(cur) + iter_y[i];
int tmp_x = get<1>(cur) + iter_x[i];
//만약 범위 안에 들어있다면
if(tmp_y >= 0 && tmp_x >= 0 && tmp_y < N && tmp_x < M ){
if(tmp[tmp_y][tmp_x].first != 0 && tmp[tmp_y][tmp_x].first != -1 ){
if(tmp[tmp_y][tmp_x].first == 2 || tmp[tmp_y][tmp_x].first == 1 ){
tmp[tmp_y][tmp_x].first = tmp[get<0>(cur)][get<1>(cur)].first;
tmp[tmp_y][tmp_x].second = get<2>(cur) + 1;
q.push(make_tuple(tmp_y,tmp_x,get<2>(cur) + 1));
isVisited[tmp_y][tmp_x] = true;
}
else{
if(tmp[tmp_y][tmp_x].first == 12 / tmp[get<0>(cur)][get<1>(cur)].first && tmp[tmp_y][tmp_x].second == get<2>(cur)+1 ){
tmp[tmp_y][tmp_x].first = -1;
tmpAnswer++;
}
}
}
}
}
}
}
만약 현재 내가 0이 아니고 -1(꽃) 이 아니라면
나를 기준으로 4방향의 위치 중에서 범위를 벗어나지 않은 곳 중에
0과 -1이 아니고
1 혹은 2 중에 하나라면 해당 땅에 배양액을 퍼트리고
내가 3일 때 해당 땅이 4이거나 내가 4일 때 해당 땅이 3인 경우이며 나와 같은 시간에 도달한 것이라면
해당 땅에 꽃을 피운다.
시간을 관리하는 것은 별도의 변수를 하나 정해 놓는 방법을 사용했는데, 처음에 배치한 배양액들은 0부터 시작하고, queue에 들어간 배양액들이 다른 칸에 배양액을 퍼트릴 때마다 1씩 증가시키게 되면 초가 흘러가는 것으로 구현할 수 있다.
다만 한 가지 궁금한 것은, 순열과 조합을 구하는 과정에서 직접 백트랙킹을 이용한 경우에는 시간 초과가 발생했지만 STL의 next_permutation을 이용한 경우에는 정상적으로 정답이 나왔다. 이 이유를 찾으면 따로 업데이트 할 예정이다.
++++추가
백트랙킹을 이용한 경우 시간 초과가 발생하는 이유를 찾았다.
바로 btk2 함수에서 발생한 문제였다.
나는 배양액들을 배열에 담을 때 {3,3,4,4,4,4} 와 같이 담았는데,
이 경우 첫 번째 3 과 두 번째 3 이 다르게 처리가 되서 그런거였다.
이 문제를 해결하기 위해서는 중복되는 원소를 처리해줘야 하는데, 같은 자리수 내에서 직전에 뽑았던 원소를 또 뽑을 수 없도록 하면 된다.
예를 들어 첫 번째 자리에 첫 번째 원소인 3을 뽑은 경우, 백트랙킹을 통해 모든 경우의 수를 확인하고 두 번째 원소를 뽑기 위해 넘어갔을 때 첫 번째 원소와 같은 값인 3이 또 있다면 뽑지 않고 넘어가게 만드는 것이다. 첫 번째 자리에 3을 뽑고 그 다음 차례에 또 3을 뽑는 것은 첫 번째 3과 두 번째 3을 다른 것으로 취급해 중복되는 조합을 여러번 확인하게 되기 때문이다.
백트랙킹을 이용한 코드
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int N, M, G, R;
pair<int,int> garden[51][51];
bool isGarden[51][51];
vector<pair<int,int> > yellow;
vector<int> seeds;
vector<bool> isUsed;
vector<bool> isColorUsed;
pair<int,int> combination[10];
int colorComb[10];
int answer = 0;
int iter_x[4] = {1,0,-1,0};
int iter_y[4] = {0,1,0,-1};
void spread(){
pair<int,int> tmp[51][51];
bool isVisited[51][51] = {false,};
int tmpAnswer = 0;
// 복사
memcpy(tmp, garden, sizeof(garden));
// for(int i=0;i<N;i++){
// for(int j=0;j<M;j++){
// tmp[i][j] = garden[i][j];
// }
// }
queue<tuple<int,int,int> > q;
// 배치
for(int i=0;i<seeds.size();i++){
int tmp_y = combination[i].first;
int tmp_x = combination[i].second;
tmp[tmp_y][tmp_x].first = colorComb[i];
tmp[tmp_y][tmp_x].second = 0;
q.push(make_tuple(tmp_y,tmp_x,0));
isVisited[tmp_y][tmp_x] = true;
}
while(!q.empty()){
tuple<int,int,int> cur = q.front();
q.pop();
if(tmp[get<0>(cur)][get<1>(cur)].first==-1) continue;
if(tmp[get<0>(cur)][get<1>(cur)].first==3 || tmp[get<0>(cur)][get<1>(cur)].first==4){
for(int i=0;i<4;i++){
int tmp_y = get<0>(cur) + iter_y[i];
int tmp_x = get<1>(cur) + iter_x[i];
//만약 범위 안에 들어있다면
if(tmp_y >= 0 && tmp_x >= 0 && tmp_y < N && tmp_x < M ){
if(tmp[tmp_y][tmp_x].first != 0 && tmp[tmp_y][tmp_x].first != -1 ){
if(tmp[tmp_y][tmp_x].first == 2 || tmp[tmp_y][tmp_x].first == 1 ){
tmp[tmp_y][tmp_x].first = tmp[get<0>(cur)][get<1>(cur)].first;
tmp[tmp_y][tmp_x].second = tmp[get<0>(cur)][get<1>(cur)].second + 1;
q.push(make_tuple(tmp_y,tmp_x,tmp[tmp_y][tmp_x].second));
isVisited[tmp_y][tmp_x] = true;
}
else{
if(tmp[tmp_y][tmp_x].first == 12 / tmp[get<0>(cur)][get<1>(cur)].first && tmp[tmp_y][tmp_x].second == tmp[get<0>(cur)][get<1>(cur)].second+1 ){
tmp[tmp_y][tmp_x].first = -1;
tmpAnswer++;
}
}
}
}
}
}
}
if(tmpAnswer > answer)
{
answer = tmpAnswer;
}
}
void btk2(int n, int start){
if(n==seeds.size()){
spread();
return;
}
int prev_num = -1;
for(int i=0;i<seeds.size();i++){
// if(n==0) cout << "hello\n";
if(!isColorUsed[i] && prev_num != seeds[i]){
isColorUsed[i] = true;
colorComb[n] = seeds[i];
prev_num = seeds[i];
btk2(n+1,i+1);
isColorUsed[i] = false;
}
// btk2(n,i+1);
// colorComb[n] = seeds[i];
// btk2(n+1,i+1);
}
}
void btk(int n,int start){
if(n == seeds.size()){
btk2(0,0);
return;
}
for(int i=start;i<yellow.size();i++){
if(!isUsed[i]){
isUsed[i] = true;
combination[n] = yellow[i];
btk(n+1,i+1);
isUsed[i] = false;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> G >> R;
for(int i=0;i<G;i++) {
seeds.push_back(3);
isUsed.push_back(false);
isColorUsed.push_back(false);
}
for(int i=0;i<R;i++){
seeds.push_back(4);
isUsed.push_back(false);
isColorUsed.push_back(false);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> garden[i][j].first;
garden[i][j].second = 0;
if(garden[i][j].first == 2) yellow.push_back(make_pair(i,j));
}
}
btk(0,0);
cout << answer << "\n";
}
next_permutation을 이용한 코드
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M, G, R;
pair<int,int> garden[51][51];
bool isGarden[51][51];
vector<pair<int,int> > yellow;
vector<int> seeds;
vector<bool> isUsed;
vector<bool> isColorUsed;
pair<int,int> combination[10];
int colorComb[10];
int answer = 0;
vector<int> landPickidx;
int iter_x[4] = {1,0,-1,0};
int iter_y[4] = {0,1,0,-1};
void simulation(){
pair<int,int> tmp[51][51];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
tmp[i][j] = garden[i][j];
}
}
// 복사
// memcpy(tmp, garden, sizeof(garden));
// 땅 조합
do{
vector<pair<int,int> > landPick;
for(int i=0;i<landPickidx.size();i++){
if(landPickidx[i]==1){
landPick.push_back(yellow[i]);
}
}
// 배양액 순열
do{
bool isVisited[51][51] = {false,};
int tmpAnswer = 0;
queue<tuple<int,int,int> > q;
for(int i=0;i<landPick.size();i++){
tmp[landPick[i].first][landPick[i].second].first = seeds[i];
tmp[landPick[i].first][landPick[i].second].second = 0;
isVisited[landPick[i].first][landPick[i].second] = true;
q.push(make_tuple(landPick[i].first,landPick[i].second,0));
}
while(!q.empty()){
tuple<int,int,int> cur = q.front();
q.pop();
if(tmp[get<0>(cur)][get<1>(cur)].first==-1) continue;
if(1){
for(int i=0;i<4;i++){
int tmp_y = get<0>(cur) + iter_y[i];
int tmp_x = get<1>(cur) + iter_x[i];
//만약 범위 안에 들어있다면
if(tmp_y >= 0 && tmp_x >= 0 && tmp_y < N && tmp_x < M ){
if(tmp[tmp_y][tmp_x].first != 0 && tmp[tmp_y][tmp_x].first != -1 ){
if(tmp[tmp_y][tmp_x].first == 2 || tmp[tmp_y][tmp_x].first == 1 ){
tmp[tmp_y][tmp_x].first = tmp[get<0>(cur)][get<1>(cur)].first;
tmp[tmp_y][tmp_x].second = get<2>(cur) + 1;
q.push(make_tuple(tmp_y,tmp_x,get<2>(cur) + 1));
isVisited[tmp_y][tmp_x] = true;
}
else{
if(tmp[tmp_y][tmp_x].first == 12 / tmp[get<0>(cur)][get<1>(cur)].first && tmp[tmp_y][tmp_x].second == get<2>(cur)+1 ){
tmp[tmp_y][tmp_x].first = -1;
tmpAnswer++;
}
}
}
}
}
}
}
if(tmpAnswer > answer){
answer = tmpAnswer;
// for(int i=0;i<N;i++){
// for(int j=0;j<M;j++){
// cout << tmp[i][j].first << " ";
// }
// cout << endl;
// }
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
tmp[i][j] = garden[i][j];
isVisited[i][j] = false;
}
}
}while(next_permutation(seeds.begin(), seeds.end()));
}while(next_permutation(landPickidx.begin(), landPickidx.end()));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> G >> R;
for(int i=0;i<G;i++) {
seeds.push_back(3);
isUsed.push_back(false);
isColorUsed.push_back(false);
}
for(int i=0;i<R;i++){
seeds.push_back(4);
isUsed.push_back(false);
isColorUsed.push_back(false);
}
for(int i=0;i<G+R;i++){
landPickidx.push_back(1);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> garden[i][j].first;
garden[i][j].second = 0;
if(garden[i][j].first == 2) yellow.push_back(make_pair(i,j));
}
}
for(int i=0;i<yellow.size()-(G+R);i++){
landPickidx.push_back(0);
}
sort(landPickidx.begin(),landPickidx.end());
simulation();
cout << answer << "\n";
}
댓글남기기