백준 18809 Gaaaaaaaaaarden

최근에 열린 백준 대회의 삼성 코딩테스트 모의고사 두번째 문제입니다.

 

주어진 땅에 초록색 빨간색 배양액을 먼저 뿌리고 이 배양액들이 상하좌우로 퍼져갑니다.

 

이때 동일 시간에 서로 만나게 되면 꽃이피게 되고 배양액을 잘 뿌렸을때 최대의 꽃 개수를 구하는 문제입니다.

 

먼저 배양액을 뿌릴 순서를 정해야 하는데 입력 받을때 배양액을 뿌릴 수 있는 땅의 개수를 세준뒤 그 개수만큼 벡터를 0으로 초기화 시켜줍니다. 이후 초록색 배양액의 숫자만큼 처음에 3을 채워주고 나머지 빨간색 배양액의 숫자만큼 4를 채워주고 정렬을 한번 합니다. 이후 이배열을 next_permutation 해주면 모든 경우의 수를 한번씩 해볼 수 있습니다. 

 

각 인덱스에 해당하는 배양액을 채워준뒤 bfs를 돌리면 됩니다. bfs에서는 cur이라는 배열을 하나둬서 동일 시간초인지 기록을 하는데 동일 시간초이면서 다른색깔의 배양액이 들어오는 순간 꽃이 필수 있습니다. 따라서 이를 잘 처리해주면 문제를 해결 할 수 있습니다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int nextx[4] = {1,0,-1,0};
int nexty[4] = {0,1,0,-1};
int garden[51][51];
int N,M,G,R;
queue<pair<int,int> > q;
int ans;
int cur[51][51];

void bfs() {

    memset(cur, 0 , sizeof(cur));
    int cnt = 1;
    int flower = 0;
    while(!q.empty()) {

        int len = q.size();

        for(int k = 0; k < len; k++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(cur[x][y] == -1) continue; //flower

            for(int i = 0; i < 4; i++) {
                   int xx = x + nextx[i];
                   int yy = y + nexty[i];

                   if(xx > N-1 || xx < 0 || yy > M-1 || yy < 0) continue;
                   if(garden[xx][yy] == 0) continue;


                   if(garden[xx][yy] == 2 || garden[xx][yy] == 1) {
                        q.push({xx,yy});
                        garden[xx][yy] = garden[x][y];
                        cur[xx][yy] = cnt;
                   }
                   else if(cur[xx][yy] == cnt && garden[xx][yy] != garden[x][y]) {
                        garden[xx][yy] = 0;
                        cur[xx][yy] = -1;                 
                        flower++;
                   }
            }
        }
        cnt++;
    }
    ans = max(ans, flower);
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M >> G >> R;

    int cnum = 0;
    int cgarden[51][51];
    vector<pair<int, int> > pos;
    //0은 호수 1은 배양액 뿌릴수 없는 땅, 2는 배양액 가능
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) {
            cin >> garden[i][j];
            cgarden[i][j] = garden[i][j];
            if(garden[i][j] == 2) {
                cnum++;
                pos.push_back({i, j});
            }
        }


    vector<int> color(cnum, 0);

    for(int i = 0; i < G+R; i++) {
        if(i < G) color[i] = 3;
        else color[i] = 4;
    }

    sort(color.begin(), color.end());
    do {
        for(int i = 0; i < cnum; i++) {
            if(color[i] != 0) {
                int x = pos[i].first;
                int y = pos[i].second;
                garden[x][y] = color[i];
                q.push({x,y});
            }
        }
        bfs();
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                garden[i][j] = cgarden[i][j];

    }while(next_permutation(color.begin(), color.end()));

    cout<<ans;

    return 0;
}