[Algorithm] Baekjoon 18809번 : Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

#define FLOOR 0x3f3f3f3f
 
struct Node
{
    int y = -1;
    int x = -1;
    int color = -1;
    int time = -1;
};
 
int r, c, greenNum, redNum;
int arr[51][51] = { 0 };
Node tempMap[51][51];
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[11] = { false };
vector<Node> validGrounds;
vector<Node> prevAddedGreenNodes;
vector<Node> prevAddedRedNodes;
int prevAddedNodes = 0; 
int turnMaxFloorCount = 0;
int maxFloorCount = 0;
vector<Node> selectedGreenNodes;
vector<Node> selectedRedNodes;
 
 
void diffuseGreenNodes()
{
    queue<Node> q;
 
    for (int i = 0; i < prevAddedGreenNodes.size(); ++i)
    {
        Node node = prevAddedGreenNodes[i];
 
        if (tempMap[node.y][node.x].time == FLOOR) continue;
 
        q.push(node);
        tempMap[node.y][node.x] = node;
    }
 
    prevAddedGreenNodes.clear();
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curTime = q.front().time;
 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (arr[nextY][nextX] == 0) continue; // 호수부분도 안됨.
            if (tempMap[nextY][nextX].time != -1) continue; // 이미 탐색한곳. 초록이든,레드든
            if (tempMap[nextY][nextX].time == FLOOR) continue; // 꽃핀곳 넘기기
 
            Node node = { nextY, nextX, 1, curTime + 1 };
            tempMap[nextY][nextX] = node;
 
            ++prevAddedNodes;
            prevAddedGreenNodes.push_back(node);
 
        }
    }
 
}
 
void diffuseRedNodes()
{
    queue<Node> q;
 
    for (int i = 0; i < prevAddedRedNodes.size(); ++i)
    {
        Node node = prevAddedRedNodes[i];
        q.push(node);
        tempMap[node.y][node.x] = node;
    }
 
    prevAddedRedNodes.clear();
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curTime = q.front().time;
 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (arr[nextY][nextX] == 0) continue; // 호수부분도 안됨.
            if (tempMap[nextY][nextX].time == FLOOR) continue; // 꽃핀곳 넘기기
            if (tempMap[nextY][nextX].color == 2) continue; // 자기자신(레드)면 continue
 
            if (tempMap[nextY][nextX].time == -1) // 탐색안한곳이면 걍 뿌리기.
            {
                Node node = { nextY,nextX,2,curTime + 1 };
                tempMap[nextY][nextX] = node;
 
                ++prevAddedNodes;
                prevAddedRedNodes.push_back(node);
                continue;
            }
 
            if (tempMap[nextY][nextX].color == 1) // 그린인데
            {
                if (tempMap[nextY][nextX].time == curTime + 1) // 동시 시간대면
                {
                    tempMap[nextY][nextX].time = FLOOR;
                    ++turnMaxFloorCount;
                }
            }
        }
    }
}
 
void diffuse()
{
 
    for (int i = 0; i < 51; ++i)
    {
        for (int j = 0; j < 51; ++j)
        {
            tempMap[i][j] = { -1,-1,-1,-1 };
        }
    }
 
    for (int i = 0; i < selectedGreenNodes.size(); ++i)
    {
        Node node = { selectedGreenNodes[i].y, selectedGreenNodes[i].x, 1, 0 };
        prevAddedGreenNodes.push_back(node);
    }
 
    for (int i = 0; i < selectedRedNodes.size(); ++i)
    {
        Node node = { selectedRedNodes[i].y, selectedRedNodes[i].x, 2, 0 };
        prevAddedRedNodes.push_back(node);
    }
 
    turnMaxFloorCount = 0;
 
    while (1)
    {
        prevAddedNodes = 0;
 
        diffuseGreenNodes();
        diffuseRedNodes();
 
        if (prevAddedNodes == 0) break;
    }
 
    maxFloorCount = max(maxFloorCount, turnMaxFloorCount);
}
 
 
void SelectRedNode(int curIndex)
{
    if (selectedRedNodes.size() == redNum) // 모든 경우의 수를 뽑았다.
    {
        diffuse();
        return;
    }
 
    for (int i = curIndex + 1; i < validGrounds.size(); ++i)
    {
        if (visited[i]) continue;  // 그린이 뽑았던것들은 제외
 
        selectedRedNodes.push_back(validGrounds[i]);
        SelectRedNode(i);
        selectedRedNodes.pop_back();
    }
}
 
void SelectGreenNode(int curIndex)
{
    if (selectedGreenNodes.size() == greenNum)
    {
        for (int i = 0; i < validGrounds.size(); ++i)
        {
            if (visited[i]) continue;
 
            selectedRedNodes.push_back(validGrounds[i]);
            SelectRedNode(i);
            selectedRedNodes.pop_back();
        }
    }
 
    for (int i = curIndex + 1; i < validGrounds.size(); ++i)
    {
        visited[i] = true; // 레드를 위한 방문체크.
        selectedGreenNodes.push_back(validGrounds[i]);
 
        SelectGreenNode(i);
 
        visited[i] = false;
        selectedGreenNodes.pop_back();
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> r >> c >> greenNum >> redNum;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 2)
            {
                validGrounds.push_back({ i,j,0,-1 });
            }
        }
    }
 
    for (int i = 0; i < validGrounds.size(); ++i)
    {
        visited[i] = true;
        selectedGreenNodes.push_back(validGrounds[i]);
 
        SelectGreenNode(i);
 
        visited[i] = false;
        selectedGreenNodes.pop_back();
    }
 
    cout << maxFloorCount;
}

 

사실 이것저것 섞여있어서 그렇지 로직자체는 어렵지 않다.

다만 내 코드는 좀 비효율적인 면이 많긴한데.. 특히 별도로 Node원소로 이루어진 tempMap을 둔게 시간에 영향이 많이 크다. 

 

사실 이 문제는 로직자체는 어렵지 않은데, 이것저것 많이 섞여 있어서 시간이 좀 걸렸다.

먼저 배양액을 뿌릴 수 있는곳에 대하여 초록, 빨강개수만큼 가짓수를 뽑아야 한다.

그래서 먼저 초록을 뽑은 후, 나머지에 대하여 레드를 뽑게했다.

레드 마저 전부 뽑으면 그제서야 메인로직이 수행된다.

 

초록을 먼저뿌리고 빨강을 이후에 뿌린 다음 같은시간대 초록노드가 있을 경우 꽃을 피우는 식으로 했다.

각각의 행동들에 대해 걍 보이는대로 구현하고 하다보니... 코드도 수행속도도 다 별로긴하다...

아마 tempMap으로 관리하는것만 고쳐도 수행속도는 크게 개선될것 같긴한데 이런 문제들은 풀고 나면 너무 질려서..

그냥 하지않겠다.

 

그리고 경우의 수 뽑는거에 대해서는 이렇게 직접 짜지 않고 algorithm.h에 포함된 next_permutation을 사용하면 편리하다.

다른 사람 코드보니까 굉장히 코드가 간결하길래 봤더니 next_permutation을 사용하더라..

일단 인지했으니 필요할 때 나도 써먹어봐야겠다.