[BOJ] 18809번 : Gaaaaaaaaaarden (C++)

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

18809번: Gaaaaaaaaaarden

 

1번) next_permutation 함수를 이용하여 배양액을 뿌릴 수 있는 곳 중에서 어떤 좌표에 초록색을, 빨간색을 뿌릴지 결정해준다.

2번) 1번을 통해 정해진 초록색, 빨간색 배양액을 좌표에 뿌려주고 해당 조합에서의 꽃의 개수를 센다.

3번) 매번 조합 중에서 꽃의 개수가 제일 많은 경우의 꽃의 개수를 출력한다. 

 

1번 구현 방법)

입력을 받으며 값이 2인 좌표는 배양액을 뿌릴 수 있는 좌표이니 벡터 cand에 좌표를 저장한다. cand의 크기는 candz에 저장해주었다. 

그리고 next_permutation 함수를 사용하여 배양액을 뿌릴 수 있는 모든 경우를 구한다. 이 때, 초록색과 빨간색 배양액의 합이 최대 10개이므로, int brute[10]; 를 선언한다.

이제 이 brute배열에 cand의 개수가 7이고 g=1, r=4이라면 {0,0,1,2,2,2,2} 으로 되도록 값을 채운다. 

매번 만들어지는 조합에서 solve함수를 출력한다. solve함수는 해당 조합에서 BFS를 돌려 꽃을 구하는 함수이다. 

 

2번 구현 방법)

solve함수는 1번 방법을 통해 정해진 초록색, 빨간색 배양액을 뿌리고 나서 꽃의 개수를 세는 함수이다. 

solve함수는 보면 이번 문제를 풀기 위한 핵심 내용이 나온다. 

pair<int,int> state[52][52]; 가 바로 그것이다. 

빨간색과 초록색이 동시에 도착하면 바로 꽃을 피우게 해줘야하므로, 매 좌표에 대해 도착시간과 배양액색깔을 저장하는 것이다. 

보통 BFS문제를 풀면 선언하는 visited배열 혹은 dist배열의 역할을 하는데 시간뿐만 아니라 배양액 색깔을 함께 저장해준다는 차이점이 있다. 

brute함수를 이용하여 초록색이나 빨간색인 경우, 해당 좌표를 모두 큐에 넣어준다.

배양액을 뿌린 좌표를 모두 넣었으니 bfs를 시작해주면 된다. 

해당 좌표가 꽃이라면 넘어간다.

상하좌우를 살펴보면서 다음 좌표가 아직 아무것도 뿌려지지 않은 땅이라면 state를 업데이트해주고 큐에 좌표를 넣어준다.

다음 좌표가 초록색 배양액이 뿌려진 좌표라면, 현재 배양액이 빨간색이면서 서로 같은 시간에 도착한다면 해당 좌표는 꽃을 피운 칸이므로 state를 업데이트해주고 꽃의 개수를 하나 센다.

반대로 다음 좌표가 빨간색 배양액이 뿌려진 좌표라면, 위의 과정처럼 검사해주고 업데이트 해주면 된다. 

 

(코드가 길어보이지만, 최대한 이해하기 쉽게 하기 위한 주석 때문에 많아보이는 것이다. 

실제 코드만 따지고 보면 그렇게 길지 않으니 포기하지 말고 잘 이해하길 바란다!)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define X first
#define Y second

int n,m,g,r;
int board[52][52];
vector<pair<int,int>> cand; //배양액을 뿌릴 수 있는 좌표
int candz; //cand의 크기
const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;
int brute[10]; //next_permutation을 위한 변수, 배양액을 뿌릴 수 있는 땅은 10개 이하임
               //cand가 7이고 g=1,r=4 일때 {0,0,1,2,2,2,2}
int mx=-1; //최대 개수의 꽃을 피울 수 있는 경우일 때, 꽃의 개수 (=답)
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int solve(){
    //2. 1번을 통해 정해진 green, red 배양액을 뿌리고 이번 조합에서의 꽃의 개수를 셈

    //***이번문제의 핵심아이디어
    //매 좌표에 도착시간과 배양액 색깔을 저장할 state를 선언함
    //보통 bfs문제에서 썼던 visited배열 대신 state를 쓰는 것임 
    pair<int,int> state[52][52]; //도착시간, 배양액 색깔
    queue<pair<int,int>> q;
    
    //이번 조합으로 뽑힌 좌표는 초록,빨강 배양액을 뿌릴 수 있는 좌표임
    //매번 조합에서 피울 수 있는 꽃의 개수를 구해야함
    //배양액을 넣기로 정해진 좌표를 모두 큐에 넣음 
    for(int i=0; i<candz; i++){
        if(brute[i]==0) continue;
        state[cand[i].X][cand[i].Y] = {0, brute[i]};
        q.push({cand[i].X, cand[i].Y});
    }
    int cnt=0; //이번 조합에서 꽃의 개수 

    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int curtime = state[cur.X][cur.Y].X;
        int curcolor = state[cur.X][cur.Y].Y;
        if(curcolor == FLOWER) continue; //꽃이면 넘어감

        for(int dir=0; dir<4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx<0||nx>=n||ny<0||ny>=m) continue; //범위를 벗어나면 넘어감
            if(board[nx][ny]==0) continue; //호수면 넘어감 

            //state의 값은 0,0으로 초기화되므로 처음 방문하는 좌표
            if(state[nx][ny].Y==EMPTY){ 
                state[nx][ny]={curtime+1, curcolor};
                q.push({nx,ny});
            }
            //같은 좌표에 초록색배양액과 빨간색배양액이 동시에 도착한 경우
            else if(state[nx][ny].Y==GREEN){
                if(curcolor==RED && state[nx][ny].X==curtime+1){ 
                    state[nx][ny].Y = FLOWER;
                    cnt++;
                }
            }
            else if(state[nx][ny].Y==RED){
                if(curcolor==GREEN && state[nx][ny].X==curtime+1){
                    state[nx][ny].Y = FLOWER;
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> g >> r; 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>board[i][j];
            if(board[i][j]==2) cand.push_back({i,j});
        }
    }

    candz = cand.size();

    //1.next_permutation함수를 이용하여 후보군 cand 중 어떤 좌표에
    //green을, red를 뿌릴지 결정해줘야함

    //그러기 위해서 brute배열을 초기화해야함
    //brute배열에 cand가 7이고 g=1,r=4 이라면 {0,0,1,2,2,2,2}로 채워줘야함
    fill(brute+candz-g-r, brute+candz-r, GREEN);
    fill(brute+candz-r, brute+candz, RED);
    do{
        int cnt = solve();
        mx = max(mx, cnt);
    }while(next_permutation(brute, brute+candz));

    cout<<mx;
}

 

추가로 이 문제를 BOJ 4179번:불! 처럼 초록색 배양액을 먼저 bfs돌리고 빨간색 배양액 bfs를 돌려서같은 시간에 도착곳에 꽃을 피우면 안되나? 라는 생각을 하면 틀린다.

문제에 나와있는 경우를 예제로 들어보겠다. 

x	x	x	x	1
x	x	x	x	0
3	2	1	2	1
2	1	0	x	2
x	2	x	x	3

[초록색 배양액 bfs를 돌리고 난 후]

x	x	x	x	4
x	x	x	x	3
1	1	0	1	2
0	1	1	x	3
x	2	x	x	4

[빨간색 배양액 bfs를 돌리고 난 후]

 

(3,1) 좌표에 꽃이 정상적으로 피지만, (4,1)에도 피게 된다. 

꽃이 피고 나면 배양액이 더이상 확산할 수 없기 때문에 (4,1)에 꽃이 피면 안된다.

그렇기에 이 문제는 초록색과 빨간색 배양액을 동시에 bfs 돌려야줘야 하고 따로 돌려줄 수 없다. 

 

 

 

 

회고) 정말정말정말 상당한 난이도가 있던 문제이고 처음보는 유형의 BFS여서 어떻게 풀어야할지 감도 안왔다. (풀어본 BFS문제 중에서 젤루다가 어려웠음.,,) 빨간색과 초록색을 동시에 bfs를 돌려야하는데 그걸 어떻게 해야될지에 대한 아이디어가 전혀 없었다. 시간만 저장하는 visited배열을 두는 대신 시간과 색깔을 동시에 저장만 하면 되는 문제였다. 정말 좋은 아이디어이다. 꼭 내것으로 만들어서 다음과 같이 동시에 bfs를 돌려줘야 하는 문제에서 쓸 수 있도록 해야겠다.