어흥
[백준 18809] Gaaaaaaaaaarden (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/18809
1. 주의할 점
- DFS를 2번 수행후 BFS를 통해 검사한다.
- BFS를 수행할 때마다 Dup배열을 초기화해야 한다(초기화 사용하지 않는 방법을 찾으면 시간단축 가능)
2. 구현
- DFS를 통해 배양액을 뿌릴 곳을 찾는다 (DFS)
- 찾은 위치에 빨간 배양액을 뿌릴것인지 초록 배양액을 뿌릴 것인지 정한다 (DFS)
- BFS를 통해 심을 수 있는 꽃의 최대를 구한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int arr[50][50];
int dup[50][50]; //빨간색 심어질 때: 10, 초록색 심어질 때: 20, 꽃: 100
int row, col, red, green, result = 0;
struct info {
int x, y;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
vector<info> can_plant, r, g;
vector<int> v; //어떤 부분에 배양액을 심을 것인지
void bfs() {
int t_result = 0;
vector<info> flower;
queue<info> rr, gg;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
dup[i][j] = arr[i][j];
for (int i = 0; i < r.size(); i++) {
tmp.x = r[i].x;
tmp.y = r[i].y;
rr.push(tmp);
dup[tmp.y][tmp.x] = 0;
}
for (int i = 0; i < g.size(); i++) {
tmp.x = g[i].x;
tmp.y = g[i].y;
gg.push(tmp);
dup[tmp.y][tmp.x] = 0;
}
while (1) {
queue<info> nr, ng;
//빨간색 퍼트린다
int len = rr.size();
for (int i = 0; i < len; i++) {
int cx = rr.front().x;
int cy = rr.front().y;
rr.pop();
if (dup[cy][cx] == 100) continue; //꽃이 피어난 자리면
dup[cy][cx] = 0; //늦게 온 초록이랑 꽃이 되지 않도록 하기 위해 못가는 곳으로 초기화
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < col && ny < row && dup[ny][nx] == 1) {
tmp.x = nx;
tmp.y = ny;
nr.push(tmp);
dup[ny][nx] = 10;
}
}
}
//초록색 퍼트린다
len = gg.size();
for (int i = 0; i < len; i++) {
int cx = gg.front().x;
int cy = gg.front().y;
gg.pop();
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < col && ny < row) {
if (dup[ny][nx] == 1) { //아직 방문하지 않은 곳
tmp.x = nx;
tmp.y = ny;
dup[ny][nx] = 0; //더이상 못가는 곳으로 바꾼다
ng.push(tmp);
}
else if (dup[ny][nx] == 10) { //꽃 생성
dup[ny][nx] = 100;
t_result++;
}
}
}
}
rr = nr;
gg = ng;
if (gg.empty() && rr.empty()) break;
}
result = max(result, t_result);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> row >> col >> green >> red;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
if (arr[i][j] == 2) {
tmp.x = j;
tmp.y = i;
can_plant.push_back(tmp);
arr[i][j] = 1;
}
}
vector<int> t;
for (int i = 0; i < can_plant.size() - red - green; i++)
t.push_back(0);
for (int i = 0; i < red + green; i++)
t.push_back(1);
do {
v.clear();
for (int i = 0; i < can_plant.size(); i++)
if (t[i] == 1)
v.push_back(i);
vector<int> tt;
for (int i = 0; i < red; i++) tt.push_back(0);
for (int i = 0; i < green; i++) tt.push_back(1);
do {
r.clear();
g.clear();
for (int i = 0; i < tt.size(); i++) {
if (tt[i] == 0) { //빨간색 배양액 시작할곳
tmp.x = can_plant[v[i]].x;
tmp.y = can_plant[v[i]].y;
r.push_back(tmp);
}
else { //초록색 배양액 시작할곳
tmp.x = can_plant[v[i]].x;
tmp.y = can_plant[v[i]].y;
g.push_back(tmp);
}
}
bfs();
} while (next_permutation(tt.begin(), tt.end()));
} while (next_permutation(t.begin(), t.end()));
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 15653] 구슬 탈출 4 (C++) (0) | 2020.03.23 |
---|---|
[백준 2011] 암호코드 (C++) (0) | 2020.03.23 |
[백준 18808] 스티커 붙이기 (C++) (2) | 2020.03.21 |
[백준 1600] 말이 되고픈 원숭이 (C++) (0) | 2020.03.20 |
[백준 13913] 숨바꼭질 4 (C++) (0) | 2020.03.19 |
Comments