18809. Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

 

풀이

필요 알고리즘: BFS, 백트래킹

 

문제를 보면 배양액이 퍼져 나가는 부분은 BFS를, 배양액을 뿌려서 피울 수 있는 꽃의 최대 개수를 구하는 부분은 백트래킹을 연상케 한다. 그러면 이 방법으로 어떻게 해결해나갈지 차례대로 접근해 보자.

 

먼저 정원에 대한 정보를 받는데, 이때 배양액을 뿌릴 수 있는 땅의 좌표를 별도의 배열 liquid에 저장해 둔다. 배양액을 뿌릴 땅을 백트래킹으로 정하기 위한 범위를 한정하기 위함이다.

 

그리고 liquid에서 배양액을 뿌릴 땅을 골라야 하는데, next_permutation 함수와 배열 mask를 이용한 백트래킹을 활용하자. 배열 mask에는 liquid에 저장된 각 땅에 어떤 배양액을 뿌릴지에 대한 정보가 담긴 순열이 저장된다. 순열의 최대 길이는 배양액을 뿌릴 수 있는 땅의 개수(= liquid의 길이)이며, 초록 배양액을 1, 빨간 배양액을 2, 아무것도 뿌리지 않음을 0으로 정의할 것이다. 만약 배양액을 뿌릴 수 있는 땅이 5개이고 초록 배양액이 2개, 빨간 배양액이 1개라고 하면 배열 mask의 초기값은 {0, 0, 1, 1, 2}와 같다. 이 경우에는 liquid의 2, 3번째 인덱스의 땅에는 초록 배양액을, 4번째 인덱스의 땅에는 빨간 배양액을 뿌린다는 뜻이다. 이 순열을 next_permutation 함수로 계속 다음 순열로 바꿔가며 마지막이 될 때까지 BFS를 시행하면 된다.

 

어느 땅에 어떤 배양액을 뿌릴지 정했으니 BFS를 시행하자. BFS에서 칸을 방문했는지 정보를 저장하는 배열을 visit라고 하면, 앞에서 정한 땅의 좌표에 값을 넣고, 그곳을 시작점으로 삼는다. 필자는 배양액이 두 종류라는 것에 착안해서, 걸린 시간을 초록 배양액은 양수로, 빨간 배양액은 음수로 저장하였다. 이러면 두 배양액이 어느 칸에 동시에 퍼졌을 경우를 (초록 배양액의 걸린 시간) + (빨간 배양액의 걸린 시간) = 0 인 것으로 판별할 수 있다. 꽃이 피어난 칸은 매우 큰 수를 집어넣어 더 이상 방문 불가능한 칸이 되도록 하였다.

 

그렇게 각 BFS를 시행하고, 그때마다 피어난 꽃의 개수를 최댓값으로 바꿔 나가면 된다.

 

소스코드

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
#define X    first
#define Y    second
#define GREEN    1		// 초록 배양액(양수)
#define RED      (-1)		// 빨간 배양액(음수)
#define BLOOM    100000		// 꽃이 핀 상태(50 * 50보다 큰 수)
using namespace std;

int n, m, g, r;
int garden[50][50];
vector<pair<int, int>> liquid;
int mask[10];
int visit[50][50];
queue<pair<int, int>> q;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int ans, tmp;

// BFS를 실행하기 전에 관련 변수를 초기화하는 함수
void initialize() {
    tmp = 0;
    for(int i = 0; i < n; i++) {
        fill(visit[i], visit[i] + m, 0);
    }
}

// BFS에서 탐색하는 칸이 유효한 범위인지 확인하는 함수
bool validRange(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// BFS를 실행하는 함수
void bfs() {
    while(!q.empty()) {
        int curx = q.front().X;
        int cury = q.front().Y;
        q.pop();
        
        if(visit[curx][cury] == BLOOM) continue;
        int color = visit[curx][cury] > 0 ? GREEN : RED;
        
        for(int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];
            
            if(!validRange(nx, ny) || garden[nx][ny] == 0 || visit[nx][ny] == BLOOM) continue;
            if(visit[nx][ny] == 0) {
                visit[nx][ny] = visit[curx][cury] + color;
                q.emplace(nx, ny);
            }
            else if(visit[curx][cury] + visit[nx][ny] + color == 0) {
                visit[nx][ny] = BLOOM;
                tmp++;
            }
        }
    }
}

int main() {
    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 >> garden[i][j];
            if(garden[i][j] == 2) liquid.emplace_back(i, j);
        }
    }
    
    int size = liquid.size();
    fill(mask + size - (g + r), mask + size - r, 1);
    fill(mask + size - r, mask + size, 2);
    do {
        initialize();
        for(int i = 0; i < size; i++) {
            if(mask[i] == 1) {
                visit[liquid[i].X][liquid[i].Y] = GREEN;
                q.emplace(liquid[i].X, liquid[i].Y);
            }
            else if(mask[i] == 2) {
                visit[liquid[i].X][liquid[i].Y] = RED;
                q.emplace(liquid[i].X, liquid[i].Y);
            }
        }
        
        bfs();
        ans = max(ans, tmp);
    } while(next_permutation(mask, mask + size));
    
    cout << ans;
    return 0;
}

실행 시간: 280 ms

사용 메모리: 2044 KB