백준 g1 18809 Gaaaaaaaaaarden c++

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

18809번: Gaaaaaaaaaarden

 

풀이

 

1. 큐 2개 동시에 돌리기

Red 배양액과 Green 배양액이 있는데, 둘이 서로에게 영향을 주므로 하나를 다 bfs 돌려놓고 다른 하나 마저 돌리기 이런 게 안 된다. 동시에 돌려야 한다.

 

BFS는 거리가 1인 칸 모두 방문 -> 2인 칸 모두 방문 -> 3인 칸 모두 방문 ... 

이렇게 거리순으로 방문을 하고, 거리가 1인 칸을 방문 할 때 거리가 2인 칸이 큐에 쌓이는 특징이 있다.

이를 활용해서 Q_size를 저장해놓고, 그 저장해놓은 size만큼만 큐에서 빼내면 거리가 1인 칸들만 순회할 수 있다. 

Q.size() 함수에서는 Q의 size가 실시간으로 늘어나므로 반드시 Q_size를 미리 저장해놓아야 한다.

이렇게 하면 거리(시간) 순서대로 두 개의 큐를 동시에 돌릴 수 있다.

 

Red Queue를 먼저 돌려놓고, Green Queue를 돌리면서 같은 시간대에 Red 배양액을 만난다면 꽃을 생성하도록 한다.

 

수도 코드

RQ_size, GQ_size 미리 저장
// RQ 돌리기
for(RQ_size)
	nx, ny
    if nx, ny가 범위 밖이거나 / board == 0(호수) 이거나 / flower == 3(꽃) 이면 -> continue
    if RVis > 0 or GVis > 0 -> contiue
    
    RVis 체크
    RQ.push(nx, ny);
    
// GQ 돌리기
for(GQ_size)
	nx, ny
    if nx, ny가 범위 밖이거나 / board == 0(호수) 이거나 / flower == 3(꽃) 이면 -> continue
    if RVis(nx, ny) == GVis(현재칸)+1
    	flower(nx, ny) 체크
        answer++
        continue
    if RVis > 0 or GVis > 0 -> contiue
    
    GVis 체크
    GQ.push

 

 

2. 배양액을 뿌릴 수 있는 칸에 Red 배양액, Green 배양액 배치하기

배양액을 뿌릴 수 있는 칸이 최대 10개이므로, next_permutation을 이용해 모든 경우의 수를 탐색해준다.

vector<int> comb;		//next_permutation을 위한 vector, Red:0, Green:1, 빈칸:2
				//ex. 전체 칸 5개에 R 1개 G 2개면 0 1 1 2 2로 들어가 있음
vector<pair<int, int>> yellow; // yellow 칸 위치 저장 (x, y)

void input() { // 배양할 수 있는 칸 만나면 yellow에 push
	for(i, j : board)
    	if board[i][j] == 배양할 수 있는 칸
        	yellow.push(i, j)
}

void combToQueue() { // comb: 0 1 1 2 2 -> yellow칸 (x, y)으로 매핑하고,
			 // 매핑된 좌표값을 Q에 push
    for (int i = 0; i < comb.size(); i++) {
        if (comb[i] == 0) { // 해당 칸에 R 배양액 시작
            int x, y;
            tie(x, y) = yellow[i];

            RVis[x][y] = 1;
            RQ.push({x, y});
        } else if (comb[i] == 1) { // 해당 칸에 G 배양액 시작
            int x, y;
            tie(x, y) = yellow[i];

            GVis[x][y] = 1;
            GQ.push({x, y});
        }
    }
}


// main
do {
        combToQueue(); // comb -> GQ, RQ, Q 시작값 세팅
        int res = BFS();

        mx = max(mx, res);
} while (next_permutation(comb.begin(), comb.end()));

 

전체 흐름

1. next_permutation을 위한 comb 벡터 (몇 번째 노랑 칸에 R or G가 들어있는지)
2. 몇 번째 노랑 칸 -> 실제 좌표 로 매핑하기 위한 yellow 벡터 (yellow[i] = i번째 노랑칸의 x, y좌표)
3. RQ, GQ의 크기를 미리 저장해놓은 RQ_size, GQ_size
   1. RQ_size만큼만 Red BFS, GQ_size만큼만 Green BFS를 수행함으로써 시간별로 BFS 돌리기 가능
4. Red BFS 먼저 하고, Green BFS를 하며 같은 시간(거리)인 Red Vis 만나면 꽃 피웠다 표시 (flower[x, y] 배열)

 

 

 

전체 소스 코드

/*boj g1 18809 Gaaaaaaaaaarden*/
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define MAXN 55
using namespace std;

int N, M, G, R;
int board[MAXN][MAXN]; // 0 호수 1 배양액X 흰색 2 배양액O 노랑 3 꽃
int RVis[MAXN][MAXN];
int GVis[MAXN][MAXN];
int flower[MAXN][MAXN];
int yCnt = 0;

vector<int> comb;              // 0: R /1: G /2: 빈 공간
vector<pair<int, int>> yellow; // yellow칸 순서

queue<pair<int, int>> GQ;
queue<pair<int, int>> RQ;

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

int mx = 0;

void printVis() {
    cout << "\n=========Green========\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << GVis[i][j] << " ";
        }
        cout << "\n";
    }

    cout << "\n=========Red========\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << RVis[i][j] << " ";
        }
        cout << "\n";
    }
}

void input() {
    cin >> N >> M >> G >> R;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] == 2) {
                yCnt++;
                yellow.push_back({i, j});
            }
        }
    }
}

void makeComb() {
    for (int t = 0; t < R; t++)
        comb.push_back(0);
    for (int t = 0; t < G; t++)
        comb.push_back(1);
    for (int t = 0; t < yCnt - R - G; t++)
        comb.push_back(2);
}

void initialize() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            GVis[i][j] = 0;
            RVis[i][j] = 0;
            flower[i][j] = 1;
        }
    }

    while (!GQ.empty())
        GQ.pop();
    while (!RQ.empty())
        RQ.pop();
}

void combToQueue() {
    for (int i = 0; i < comb.size(); i++) {
        if (comb[i] == 0) { // 해당 칸에 R 배양액 시작
            int x, y;
            tie(x, y) = yellow[i];

            RVis[x][y] = 1;
            RQ.push({x, y});
        } else if (comb[i] == 1) { // 해당 칸에 G 배양액 시작
            int x, y;
            tie(x, y) = yellow[i];

            GVis[x][y] = 1;
            GQ.push({x, y});
        }
    }
}

int BFS() {
    int answer = 0;
    while (!RQ.empty() || !GQ.empty()) {
        int RQ_size = RQ.size();
        int GQ_size = GQ.size();

        for (int i = 0; i < RQ_size; i++) {
            int x, y;
            tie(x, y) = RQ.front();
            RQ.pop();

            if (flower[x][y] == 3) continue; // 꽃이 피어나면 배양액은 사라짐

            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (board[nx][ny] == 0 || flower[nx][ny] == 3) continue;

                if (RVis[nx][ny] > 0) continue;
                if (GVis[nx][ny] > 0) continue;

                RVis[nx][ny] = RVis[x][y] + 1;
                RQ.push({nx, ny});
            }
        }

        for (int i = 0; i < GQ_size; i++) {
            int x, y;
            tie(x, y) = GQ.front();
            GQ.pop();

            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (board[nx][ny] == 0 || flower[nx][ny] == 3) continue;

                if (GVis[nx][ny] > 0) continue;
                if (RVis[nx][ny] == GVis[x][y] + 1) {
                    GVis[nx][ny] = GVis[x][y] + 1;
                    flower[nx][ny] = 3;
                    answer++;
                    continue;
                }
                if (RVis[nx][ny] > 0) continue;

                GVis[nx][ny] = GVis[x][y] + 1;
                GQ.push({nx, ny});
            }
        }
        // printVis();
    }
    return answer;
}

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

    input();
    makeComb();

    do {
        initialize();
        combToQueue(); // comb -> GQ, RQ, Q 시작값 세팅
        int res = BFS();

        mx = max(mx, res);
    } while (next_permutation(comb.begin(), comb.end()));

    cout << mx << "\n";
}

 

 

예전에 이 문제를 봤었을 땐 헉 .. 어렵겠다 했는데 막상 풀어보니 별로 안 어려웠음