Gaaaaaaaaaarden

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M, G, R, ans;
int board[51][51];
int tmp[51][51];
int vis[51][51];
int ch[11];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<pair<int,int>> pos;
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)
                pos.push_back({i,j});
        }
    fill(ch, ch+pos.size(), 2);
    int k=0;
    for(;k<G;k++) ch[k] = 0; // 초록색 배양액
    for(;k<G+R;k++) ch[k] = 1; // 빨간색 배양액
    do{
        queue<pair<int,int>> green;
        queue<pair<int,int>> red;
        int Tans=0;
        for(int i=0;i<N;i++)
            fill(vis[i], vis[i]+M, 0);
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                tmp[i][j] = board[i][j];
        for(int i=0;i<pos.size();i++)
        {
            auto cur = pos[i];
            if(ch[i] == 0){
                tmp[cur.first][cur.second] = 3; // 초록색
                green.push({cur.first, cur.second});
                vis[cur.first][cur.second] = 1;
            }else if(ch[i] == 1)
            {
                tmp[cur.first][cur.second] = 4; // 빨간색
                red.push({cur.first, cur.second});
                vis[cur.first][cur.second] = 1;
            }
        }
    int flag=2;
    while(!green.empty() or !red.empty())
    {
        int gsize=green.size();
        int rsize=red.size();
        while(gsize--)
        {
            auto cur = green.front(); green.pop();
            /* 이미 꽃이 핀 자리면 종료해야함!
                --> 여기서 걸러주는 이유 ! : 밑에서 꽃이 됬지만 green의 큐에는 있기 때문 */
            if(tmp[cur.first][cur.second] == 5) continue;
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(ny<0 or nx<0 or ny>=N or nx>=M) continue;
                if(tmp[ny][nx] == 0 || vis[ny][nx]) continue;
                green.push({ny, nx});
                vis[ny][nx] = flag;
                tmp[ny][nx] = 3;
            }
        }
        while(rsize--)
        {
            auto cur = red.front(); red.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(ny<0 or nx<0 or ny>=N or nx>=M) continue;
                if(tmp[ny][nx] == 0 || (vis[ny][nx]>=1 and vis[ny][nx]< flag)) continue;
                if(tmp[ny][nx] == 3 and vis[ny][nx] == flag){
                tmp[ny][nx] = 5;
                vis[ny][nx] = 1;
                Tans++;
                }else{
                    red.push({ny, nx});
                    vis[ny][nx] = 1;
                    tmp[ny][nx] = 4;
                }
            }
        }
        flag++;
    }
    ans = max(ans, Tans);
    }while(next_permutation(ch, ch+pos.size()));
    cout << ans;
    return 0;
}

• 로직
  1) 배양액을 뿌릴 수 있는 땅의 수에서 R과 G의 개수만큼 뽑는 모든 조합을 구한다 (next_permutation())
  2) green과 red에 대해 BFS를 실행해서 꽃이 피는 수만큼 count!

• 어려웠던 점
  • green에서 큐를 돌릴 때 꽃이 폈는지 검사하는 걸 놓침
    (green을 먼저 돌리기 때문에 red에서 꽃이폈다고 해도, green의 큐에는 들어가있기 때문)

• 깨달은 것
  • 서로 영향을 주는 2개의 BFS구현시 원래 하던 방법(임시 queue 생성)이 아니라 size를 이용한 더 간단한 방법을 발견함

   while(!green.empty() or !red.empty())
    {
        int gsize=green.size();
        int rsize=red.size();
        while(gsize--)
        {
           // 로직
        }
        while(rsize--)
        {
           // 로직
        }
    }