[C++/백준] 18809번: Gaaaaaaaaaarden

문제 링크

18809번: Gaaaaaaaaaarden

 

풀이

백트래킹이라는데 BFS에 조합 문제인 것 같다.

1. 입력을 받으면서 배양액을 뿌릴 수 있는 땅을 구해놓는다.
2. 1번에서 구한 땅에 이제 배양액을 뿌릴 차례인데, 순열로 처리한다.
   1. 종류에 따라 상수로 정의했고 (EMPTY, GREEN, RED, FLOWER)
   2. 만약 뿌릴 수 있는 땅이 7개인데 초록색 배양액이 3개, 빨간색 배양액이 2개라면, water 배열은 {0,0,1,1,1,2,2}가 될 것이고 이를 순열처리해서 구하면 모든 조합대로 배양액을 뿌릴 수 있게 된다.
3. BFS는 여느 BFS와 같이 queue를 이용해서 풀면 된다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#define INF 2501

using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;

int BFS(queue<pair<int,int>>& q, vector<vector<int>> &board, vector<vector<pair<int,int>>> &visited)
{
    int cnt = 0;
    while (!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        int curTime = visited[ty][tx].first;
        int curColor = visited[ty][tx].second;
        q.pop();
        if (curColor == FLOWER) continue;
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) continue; // 범위 밖
            if (board[ny][nx] == 0) continue; // 호수
            if (visited[ny][nx].first == INF) // 간 적 없다면
            {
                q.push({ny,nx});
                visited[ny][nx].first = visited[ty][tx].first + 1;
                visited[ny][nx].second = visited[ty][tx].second;
            }
            if (visited[ny][nx].second == GREEN)
            {
                if (curColor == RED && visited[ny][nx].first == curTime + 1)
                {
                    visited[ny][nx].second = FLOWER;
                    cnt++;
                }
            }
            else if (visited[ny][nx].second == RED)
            {
                if (curColor == GREEN && visited[ny][nx].first == curTime + 1)
                {
                    visited[ny][nx].second = FLOWER;
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, g, r;
    cin >> n >> m >> g >> r;

    vector<vector<int>> board(n, vector<int>(m));
    vector<pair<int, int>> ground; // 배양액을 뿌릴 수 있는 땅
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 2)
            {
                ground.push_back({ i,j });
            }
        }
    }

    vector<int> water;
    for (int i = 0; i < ground.size() - g - r; i++)
    {
        water.push_back(EMPTY);
    }
    for (int i = 0; i < g; i++)
    {
        water.push_back(GREEN);
    }
    for (int i = 0; i < r; i++)
    {
        water.push_back(RED);
    }

    int answer = -1;
    do
    {
        queue<pair<int, int>> q; // y, x
        vector<vector<pair<int, int>>> visited(n, vector<pair<int, int>>(m, { INF, EMPTY })); // 거리, 배양액 종류
        for (int i = 0; i < ground.size(); i++)
        {
            if (water[i] == EMPTY) continue;
            q.push({ ground[i].first, ground[i].second });
            visited[ground[i].first][ground[i].second] = { 0,water[i] };
        }
        answer = max(answer, BFS(q, board, visited));
    } while (next_permutation(water.begin(), water.end()));

    cout << answer;
}