[c++] 백준 18809번 : Gaaaaaaaaaarden

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

첫번째 코드

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

using namespace std;

struct seed {
    int y, x;
};

int map[50][50];
vector<seed> landToSeed;
vector<seed> Green;
vector<seed> Red;
int N, M, G, R;

vector<int> g;
vector<int> r;

int dir_y[4] = {0,1,0,-1};
int dir_x[4] = {1,0,-1,0};


void printVector(vector<int>& a) { // int에 land도 넣을수 있을까?
    vector<int>::iterator iter;
    for (iter = a.begin(); iter != a.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}

void printLandVector(vector<seed> a) {
    for (int i = 0; i < a.size(); i++) {
        cout << a[i].y << " " << a[i].x << endl;
    }
}

void adjustSize() {
    int dif = Red.size()/R - Green.size()/G;
    if (dif>0) { // 길이 차이가 있으면
        for (int i = 0; i < dif; i++) {
            int last = Green.size();
            for (int j = 0; j < G; j++) {
                Green.push_back(Green[last - G+j]);
            }
        }
    }
    else if (dif<0) {
        for (int i = 0; i < -dif; i++) {
            int last = Red.size();
            for (int j = 0; j < R; j++) {
                Red.push_back(Red[last - R + j]);
            }
        }
    }
}

void combi_R(int start, int land_size, vector<seed> tmp) { // 남은 수 중 R 순열 뽑기
    if (r.size() == R) {
        for (int i = r.size() - 1; i >= 0; i--) { // Red 채우기
            Red.push_back(tmp[r[i]]);
            tmp.erase(tmp.begin() + r[i]);
        }
        adjustSize();
        return;
    }
    for (int i = start + 1; i < land_size; i++) { // 10*5
        r.push_back(i);
        combi_R(i, land_size, tmp); // 5
        r.pop_back();
    }
    return;
}

void putGR() {
    vector<seed> tmp; // 구조체 vector 복사하기 (더 공부)
    for (int i = 0; i < landToSeed.size(); i++) { // 10
        seed tmp_seed; tmp_seed.y = landToSeed[i].y;  tmp_seed.x = landToSeed[i].x;
        tmp.push_back(tmp_seed);
    }

    for (int i = g.size()-1; i >= 0; i--) { // Green 채우기
        Green.push_back(tmp[g[i]]);
        tmp.erase(tmp.begin() + g[i]);
    }

    combi_R(-1, tmp.size(),tmp); // 10*5
    return;
}

void combi_G(int start, int land_size) { // G 조합 뽑기
    if (g.size() == G) {
        putGR(); // 10*5
        return;
    }
    for (int i = start + 1; i < land_size; i++) { // 10*5*10*5 => 10^3 정도
        g.push_back(i);
        combi_G(i, land_size); // 깊이 5
        g.pop_back();
    }
    return;
}

int getFlower(int** map) {
    int num = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 3) {
                num++;
            }
        }
    }
    return num;
}
bool inMap(int y, int x) {
    if (y >= 0 && x >= 0 && y < N && x < M) {
        return true;
    }
    else {
        return false;
    }
}

int Sowing() {
    vector<int> result;
    queue<seed> G_queue;
    queue<seed> R_queue;
    int size = (int)Green.size()/G;
    int flower = 0;

    cout << "g.size? " << Green.size() << endl;
    cout << "r.size? " << Red.size() << endl;

    for (int i = 0; i < size; i++) { // 10^5
        int** tmp_map = new int*[N]; // 동적 할당해서 map 복사
        for (int j = 0; j < N; j++) {
            tmp_map[j] = new int[M];
        }
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                if (map[j][k] == 2) // 안 채워진 2는 없애버리기
                    tmp_map[j][k] = 1;
                else
                    tmp_map[j][k] = map[j][k];
            }
        }

        queue<seed> empty;
        swap(G_queue, empty);
        queue<seed> empty1;
        swap(R_queue, empty1);

        int x, y;
        for (int j = 0; j < G; j++) {
            y = Green[G*i + j].y; // 초록색 배양액 뿌리기
            x = Green[G*i + j].x;
            tmp_map[y][x] =0;
            //cout << "g : "<< y <<" " << x << endl;
            G_queue.push(Green[G*i + j]);
        }

        for (int j = 0; j < R; j++) {
            y = Red[R*i + j].y; // 빨간색 배양액 뿌리기
            x = Red[R*i + j].x;
            tmp_map[y][x] = 0;
            //cout << "r : " << y << " " << x << endl;
            R_queue.push(Red[R*i + j]);
        }

        int change = 1;
        while (change) { // 변화가 없을 때까지 확산 진행
            /*
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    cout << tmp_map[j][k] << " ";
                }
                cout << endl;
            }
            cout << endl;
            */
            change = 0;
            int g_size = G_queue.size();
            for (int j = 0; j < g_size; j++) { // 초록색 배양액 확산
                int x_seed = G_queue.front().x; int y_seed = G_queue.front().y; 
                G_queue.pop();
                if (tmp_map[y_seed][x_seed] == 3) // 이미 꽃 피운 곳이면 확산능력 x
                    continue;

                for (int k = 0; k < 4; k++) {
                    x_seed += dir_x[k]; y_seed += dir_y[k];
                    if (inMap(y_seed, x_seed)) {
                        int check = tmp_map[y_seed][x_seed];
                        if (check != 0 && check != 3 && check != -1) {
                            tmp_map[y_seed][x_seed] *= -1;
                            change += 1;
                            seed tmp_seed; tmp_seed.x = x_seed; tmp_seed.y = y_seed;
                            G_queue.push(tmp_seed);
                        }
                    }
                    x_seed -= dir_x[k]; y_seed -= dir_y[k];
                }
            }
            int r_size = R_queue.size();
            for (int j = 0; j < r_size; j++) { // 빨간색 배양액 확산
                int x_seed = R_queue.front().x; int y_seed = R_queue.front().y;
                R_queue.pop();
                if (tmp_map[y_seed][x_seed] == 3) // 이미 꽃 피운 곳이면 확산능력 x
                    continue;

                for (int k = 0; k < 4; k++) {
                    x_seed += dir_x[k]; y_seed += dir_y[k];
                    if (inMap(y_seed, x_seed)) {
                        int check = tmp_map[y_seed][x_seed];
                        if (check != 0 && check != 3 && check != -3) {
                            tmp_map[y_seed][x_seed] *= -3;
                            if (tmp_map[y_seed][x_seed] == 3) { // 꽃 피웠으면
                                change -= 1; // 다음에 확산 x
                            }
                            else {
                                change += 1;
                                seed tmp_seed; tmp_seed.x = x_seed; tmp_seed.y = y_seed;
                                R_queue.push(tmp_seed);
                            }
                        }
                    }
                    x_seed -= dir_x[k]; y_seed -= dir_y[k];
                }
            }

            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tmp_map[j][k] < 0) {
                        tmp_map[j][k] = 0;
                    }
                }
            }
        }

        int flower_num = getFlower(tmp_map);
        if (flower_num > flower) {
            flower = flower_num;
            cout << flower << endl;
        }
    }
    return flower;
}

int main() {
    cin >> N >> M >> G >> R;
    int index = 0;

    for (int i = 0; i < N; i++) { // 10^3
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) { // 배양액을 뿌릴 수 있는 땅 저장
                seed tmp; tmp.y = i; tmp.x = j;
                landToSeed.push_back(tmp);
            }
        }
    }
    /*
    cout << "landToSeed first: " << endl;
    printLandVector(landToSeed);
    */
    int land_size = landToSeed.size();
    combi_G(-1, land_size); // 10^3
    cout << Sowing();


}

풀리긴 하는데 복잡하고 시간 초과

set에 넣어서 꽃피울 곳을 구하는 것으로 구현해보려고 했으나 겹치는 부분을 파악하는 것에서 set을 모두 순회해야하므로 시간 복잡도가 너무 높아진다.

성공

vector<seed>::iterator iter;
for (iter = change_set.begin(); iter != change_set.end(); iter++) {
    seed tmp = *iter;
    if(tmp_map[tmp.y][tmp.x]<0)
        tmp_map[tmp.y][tmp.x] = 0;
}

while문 안에서 O(N*M)의 이중 for문을 돌면서 음수인 위치를 찾아서 0으로 만드는 코드를 한 vector 안에 for문의 현재 루프에서 바뀐(퍼진) 배양액 위치를 저장해두어 해당 위치만 검사하고 0으로 만드는 코드로 바꾸었더니 시간 초과가 해결되었다. change_set이라는 추가로 vector는 위쪽에 정의해야한다.

코드 설명

위치를 편하게 나타내기 위해 seed라는 구조체를 사용하였음! (x 좌표, y좌표로 구성)

for (int i = 0; i < N; i++) { // 10^3
    for (int j = 0; j < M; j++) {
        cin >> map[i][j];
        if (map[i][j] == 2) { // 배양액을 뿌릴 수 있는 땅 저장
            seed tmp; tmp.y = i; tmp.x = j;
            landToSeed.push_back(tmp);
        }
    }
}

garden map을 저장하면서 동시에 배양액을 뿌릴 수 있는 땅을 landToSeed라는 vector에 저장

void combi_G(int start, int land_size) { // G 조합 뽑기
    if (g.size() == G) {
        putGR(); // 10*5
        return;
    }
    for (int i = start + 1; i < land_size; i++) { // 10*5*10*5 => 10^3 정도
        g.push_back(i);
        combi_G(i, land_size); // 깊이 5
        g.pop_back();
    }
    return;
}

combi_G => putGR => combi_R => adjustSize 함수를 거쳐 조합을 Green, Red vector에 저장

adjustSize 함수는 G가 뽑은 조합을 제외한 수 중 R이 조합을 결정하기 때문에 R의 조합 수만큼 G가 반복돼서 나와야한다. 이를 맞춰주기 위함이다. (아래의 그림에서 0,1,2가 2번 중복돼서 나오는 것)

int x, y;
for (int j = 0; j < G; j++) {
    y = Green[G*i + j].y; // 초록색 배양액 뿌리기
    x = Green[G*i + j].x;
    tmp_map[y][x] = 0;
    //cout << "g : "<< y <<" " << x << endl;
    G_queue.push(Green[G*i + j]);
}

for (int j = 0; j < R; j++) {
    y = Red[R*i + j].y; // 빨간색 배양액 뿌리기
    x = Red[R*i + j].x;
    tmp_map[y][x] = 0;
    //cout << "r : " << y << " " << x << endl;
    R_queue.push(Red[R*i + j]);
}

저장해둔 조합을 한묶음씩 꺼내와서 (Green에서 G개, Red에서 R개씩) 각각 -1, -3을 map에 넣는다. (배양액을 뿌린다.)

이 때 코드에서는 0을 넣게 되어있는데, 어차피 나중에 0으로 초기화해줄 것이라 그런 것이다.

while(change){
 // 너무 많아 생략 위의 코드에 있음
}

변화가 더이상 없을 때까지 queue에 담긴 좌표를 하나씩 꺼내가며 초록색 배양액이 퍼진 부분은 -1을 빨간색 배양액이 퍼진 부분은 -3을 저장한다. 이 때, 두 배양액이 동시에 닿아 결과가 3이 되는 부분에서는 꽃이 핀다. (꽃이 핀 것은 나중에 3인 것의 갯수를 새는 방식으로 계산한다.)

다음에 퍼질 위치를 각각 저장해서 겹치면 꽃의 갯수를 나타내는 변수를 하나씩 증가시키는 방식으로는 퍼질 위치의 갯수^2의 시간복잡도가 필요하므로 너무 시간이 오래 걸린다.

다음 루프에서는 퍼진 배양액들이 다시 사방으로 배양액을 퍼뜨릴 텐데, 순서가 헷갈리지 않도록 현재 루프에서 퍼진 배양액들은 0으로 초기화해준다. (꽃을 피울 수 없고 배양액도 퍼질 수 없는 곳이라는 의미로 그냥 호수처럼 초기화해주었다.)

깨달은 것

정답 코드를 보고 발전시킬 점을 적어보았다.

참고 : https://blog.encrypted.gg/938?category=730176

1. fill 함수 사용

fill(iter1,iter2,val); : 범위 내(first부터(last-1)까지)의 원소들을 val로 채운다.

2. 구조체를 사용할 때 따로 만들지 말고 pair 사용

본인은 따로 구조체를 만들어서 구현했으나, pair를 사용하면 그러지 않아도 된다.

pair<int,int> state[52][52];
queue<pair<int,int>> q;

3. next_permutation

조합을 구현하느라 굉장히 많은 시간을 소요하였는데, 순열을 구현하는 함수로 해결할 수 있었다 :> 하지만 조합을 구하는 함수를 처음 공부해본 것에 의의를 두기로 했다. 정답 공개 블로그에서도 조합함수를 구현하는 '백트래킹' 방법을 다른 정답으로 작성해두었다.

next_permutation(iter1, iter2); iter1에서 iter2-1까지의 순열을 구하는 함수, 호출 시마다 다음 순열로 바뀌게 해줌

 

4. bfs

초록, 빨강 배양액을 따로 확인하는 게 아니라 Queue에 들어온 배양액의 위치를 꺼내면서 사방을 순회하며 3가지 경우를 판단하였다. 이에 우선하는 조건으로 맵안에 있고, 호수가 아닌지 먼저 판단하였고, 뒤에 따르는 3가지 경우는 다음과 같다.

 

1) 색에 따른 정보가 비어있을 경우

현재 위치의 색으로 채워주고 시간을 1늘려주면 된다.

2) 빨간색 배양액이 퍼져있는 곳일 경우

현재 위치의 색이 초록색이고 검사하는 위치의 시간이 현재시간 +1이라면 현재시간에 동시에 퍼진 곳이므로 꽃이 핀다.

3) 초록색 배양액이 퍼져있는 곳일 경우

현재 위치의 색이 빨간색이고 검사하는 위치의 시간이 현재시간 +1이라면 현재시간에 동시에 퍼진 곳이므로 꽃이 핀다.

 

본인은 초록, 빨간 배양액을 따로 for문을 돌며 확인했으며 시간이 맞는 것을 확증하기 위해서 map에 초록은 -1, 빨강은 -3을 곱하도록 하여 3이 되면 꽃이 핀다고 생각하였는데, 이렇게 구현하니 배양액은 퍼졌지만 꽃은 안 핀 블록을 다음시간에 헷갈리지 않도록 0으로 초기화 시켜주어야해서 queue에 들어있는 위치에 대해 순회과정이 필요했다. 이를 해결하려면 정답처럼 시간과 색이 동시에 표현될 수 있도록 자료구조를 짜면 된다.

시간에 대한 정보도 자료구조로 표현하면 쉽다는 것을 생각치 못했다. 기본적인 bfs에서 배운 부분인데!

또한 꽃의 갯수를 확인하기 위해 전체를 순회하며 3인 곳의 갯수를 세었는데, 이를 해결하려면 꽃이 필 때마다 1씩 증가하는 변수를 두면 된다.