[백준 18809번] Gaaaaaaaaaarden

문제 링크: https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

<문제 풀이> 백트랙킹

1. 배양액을 뿌릴 수 있는 땅에 대해서 같은 것이 있는 순열(RRRGG...)을 구한다.

2. 뽑은 수열에 대해서 큐 두 개를 준비해서 빨간색 배양액, 초록색 배양액을 동시에 BFS를 진행한다.

-> 큐에는 항상 같은 레벨(같은 초)의 좌표가 들어간다.

-> BFS를 진행할 때 매 초마다  빨간색 배양액과 초록색 배양액이 동일한 시간에 만나는지 체크

-> 구현상 큐에는 꽃이 피어난 좌표도 들어갈 수 있으므로 현재 좌표가 꽃이 피어난 좌표이면 무시

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
#define X first
#define Y second
 
int dx[4] = {0 , 0, 1, -1};
int dy[4] = { 1, -1, 0, 0 };
 
int N, M, G, R;
int G_temp, R_temp;
int board[50][50];
int backup[50][50]; //board 백업용
int visited[50][50]; //배양액 방문 체크 -> 1 == R, 2 == G
int R_visited[50][50]; //R배양액 BFS 방문 체크
int G_visited[50][50]; //G배양액 BFS 방문 체크
int res = 0; // 꽃의 최대 개수
 
 
//R배양액, G배양액 퍼트리기
void BFS() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            backup[i][j] = board[i][j]; //board 배열을 다시 사용하기 위해 백업
        }
    }
    queue<pair<int, int> > red, green;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == 1) { //R 배양액이면
                red.push({ i, j });
                R_visited[i][j] = true;
            }
            else if (visited[i][j] == 2) { // G 배양액이면
                green.push({ i, j });
                G_visited[i][j] = true;
            }
        }
    }
 
    int cnt = 0; //꽃의 개수
    while (!red.empty() || !green.empty()) {
 
        int red_size = red.size();
        for (int i = 0; i < red_size; i++) {
            auto cur = red.front(); red.pop();
            if (board[cur.X][cur.Y] == 3) continue; //만약 꽃이 피어난 곳이면 무시
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                if (R_visited[nx][ny] || board[nx][ny] == 0)continue; //방문했거나 호수이면 무시
                if (board[nx][ny] == 3)continue; // 꽃이 피어난 곳은 무시
                if (G_visited[nx][ny] && G_visited[nx][ny] != R_visited[cur.X][cur.Y] + 1)continue; //배양액은 서로 다른 곳에 뿌려져야한다.
                else if (G_visited[nx][ny] && G_visited[nx][ny] == R_visited[cur.X][cur.Y] + 1) {//만약 동일한 시간에 두 배양액이 합쳐지면
                    board[nx][ny] = 3;  //꽃이 피어난다.
                    cnt++;
                    R_visited[nx][ny] = R_visited[cur.X][cur.Y] + 1;
                    continue;
                }
                R_visited[nx][ny] = R_visited[cur.X][cur.Y] + 1;
                red.push({ nx, ny });
            }
        }
 
        int green_size = green.size();
        for (int i = 0; i < green_size; i++) {
            auto cur = green.front(); green.pop();
            if (board[cur.X][cur.Y] == 3) continue; //만약 꽃이 피어난 곳이면 무시
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                if (G_visited[nx][ny] || board[nx][ny] == 0)continue; //방문했거나 호수이면 무시
                if (board[nx][ny] == 3)continue; // 꽃이 피어난 곳은 무시
                if (R_visited[nx][ny] && R_visited[nx][ny] != G_visited[cur.X][cur.Y] + 1)continue; //배양액은 서로 다른 곳에 뿌려져야한다.
                else if (R_visited[nx][ny] && R_visited[nx][ny] == G_visited[cur.X][cur.Y] + 1) {//만약 동일한 시간에 두 배양액이 합쳐지면
                    board[nx][ny] = 3;  //꽃이 피어난다.
                    cnt++;
                    G_visited[nx][ny] = G_visited[cur.X][cur.Y] + 1;
                    continue;
                }
                G_visited[nx][ny] = G_visited[cur.X][cur.Y] + 1;
                green.push({ nx, ny });
            }
        }
    }
 
    res = max(res, cnt); //최대 꽃의 개수 
 
    /*초기화*/
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            board[i][j] = backup[i][j];
            R_visited[i][j] = 0;
            G_visited[i][j] = 0;
        }
    }
}
 
//N*N 격자에서 초록색 배양액 G개, 빨간색 배양액 R개를 뽑는 조합
void dfs(int cur, int k) {
    if (k == G + R) { //초록색 배양액 G개, 빨간색 배양액 R개를 뿌렸으면
        BFS();
        return;
    }
    for (int i = cur + 1; i < N * M; i++) {
        int x = i / M;
        int y = i % M;
        if (board[x][y] == 2) { // 배양액을 뿌릴 수 있으면
            if (R_temp != 0) { // R 배양액을 다 못뿌렸으면
                R_temp--;
                visited[x][y] = 1;
                dfs(i, k + 1);
                visited[x][y] = 0;
                R_temp++;
            }
            if (G_temp != 0) { // G 배양액을 다 못뿌렸으면 
                G_temp--;
                visited[x][y] = 2;
                dfs(i, k + 1);
                visited[x][y] = 0;
                G_temp++;
            }
        }
    }
}
 
 
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> M >> G >> R;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    G_temp = G;
    R_temp = R;
    dfs(-1, 0);
    cout << res;
    return 0;
}