Problem 문제풀이
나의 부족함을 다시 한 번 깨닫게 해주는 문제였다. 간단히 설명하자면 다음과 같다.
전략
-
배양액을 뿌릴 땅을 정한다.
-
배양액이 인접한 땅으로 퍼진다.
-
서로 다른 배양액이 동시에 만날 경우 꽃이 핀다.
-
2,3을 반복한다.
문제를 풀기 위해 두 가지 기능이 필요하다.
-
배양액을 뿌릴 땅을 정하는 작업
-
배양액을 퍼뜨리는 작업
배양액을 뿌릴 땅을 정하는 함수를 이전에 풀었던 N과 M을 참고하여 만들어보자.
먼저 배양액을 뿌릴 수 있는 땅 pair<int,int> soil에서 G+R개의 땅을 선택해야한다.
그 후 선택된 땅에 초록 배양액을 뿌릴지 빨간 배양액을 뿌릴지 결정해야한다.
void solve(int index)
{
if (index == G + R)
{
solve2(0);
}
if (index < G + R)
{
for (int i = 0; i < soil.size(); i++)
{
if (used[i] == 0)
{
if (!pos.empty() && pos.back() > i)
{
continue;
}
pos.push_back(i);
used[i] = 1;
solve(index + 1);
pos.pop_back();
used[i] = 0;
}
}
}
}
solve()를 통해 G+R개의 땅을 골랐다.
이제 solve2()를 통해 적절하게 분배해보자.
void solve2(int index)
{
if (index == G)
{
for (int i = 0; i < pos.size(); i++)
{
if (used2[i] == 0)
{
r_pos.push_back(pos[i]);
}
}
tmp = simulation();
r_pos.clear();
if (ans < tmp)
{
ans = tmp;
}
return;
}
if (index < G)
{
for (int i = 0; i < pos.size(); i++)
{
if (used2[i] == 0)
{
if (!g_pos.empty() && g_pos.back() > pos[i])
{
continue;
}
g_pos.push_back(pos[i]);
used2[i] = 1;
solve2(index + 1);
g_pos.pop_back();
used2[i] = 0;
}
}
}
}
이번 문제에서 가장 실수가 많았던 부분이 solve2()의 구현이었다. ctrl+c + ctrl+v는 정말 좋은 도구이자
정말 위험한 도구이다… 이제 simulation을 구현하자. BFS를 사용할 것이고 queue에는 Growth라는 다음과 같은 struct를 사용할 것이다.
struct Growth {
int row;
int col;
int time;
int color;
Growth(int _row, int _col, int _time, int _color) :row(_row), col(_col), time(_time), color(_color) {}
};
queue에 녹색 배양액의 정보와 빨간 배양액의 정보를 담는다. 그리고 퍼뜨린다. 여기서 주의해야할 점이 몇 가지 있다.
1.초록 배양액이 먼저 퍼지고 빨간 배양액이 그 다음에 퍼진다.
따라서 빨간 배양액이 퍼질 땅에 초록 배양액이 퍼져있다면
배양액이 퍼진 시간을 확인하고 꽃을 피울지 말지 결정한다.
2.초록 배양액이 퍼질 때 꽃이 필지 안 필지는 알 수가 없다.
꽃이 피더라도 queue에 정보가 들어가는 것은 막을 수 없다.
따라서 queue에서 정보를 받아올 때 그 땅에 꽃이 폈는지 아닌지 확인을 해야한다.
int simulation()
{
int ret = 0;
pair<int, int> _garden[51][51];
queue<Growth>q;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
_garden[i][j] = { garden[i][j].first,garden[i][j].second };
}
}
for (int i = 0; i < G; i++)
{
garden[soil[g_pos[i]].first][soil[g_pos[i]].second] = { 3,0 };
q.push(Growth(soil[g_pos[i]].first, soil[g_pos[i]].second, 0, 3));
}
for (int i = 0; i < R; i++)
{
garden[soil[r_pos[i]].first][soil[r_pos[i]].second] = { 4,0 };
q.push(Growth(soil[r_pos[i]].first, soil[r_pos[i]].second, 0, 4));
}
//0 : 호수, 1 : 배양액을 뿌릴 수 없는 땅, 2 : 배양액을 뿌릴 수 있는 땅
//3 : 초록색 배양액을 뿌린 땅, 4 : 빨간색 배양액을 뿌린 땅 5 : 꽃이 핀 땅
while (!q.empty())
{
Growth growth = q.front();
q.pop();
if (garden[growth.row][growth.col].first == 5)
{
continue;
}
for (int i = 0; i < 4; i++)
{
int nR = growth.row + dirR[i];
int nC = growth.col + dirC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < M)
{
if (garden[nR][nC].first > 0 && garden[nR][nC].first < 3)
{
garden[nR][nC].first = growth.color;
garden[nR][nC].second = growth.time + 1;
q.push(Growth(nR, nC, growth.time + 1, growth.color));
}
if (growth.color == 4)
{
if (garden[nR][nC].first == 3 && garden[nR][nC].second == (growth.time + 1))
{
garden[nR][nC].first = 5;
ret++;
}
}
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
garden[i][j] = { _garden[i][j].first, _garden[i][j].second };
}
}
cout << ret << endl;
return ret;
}
실수가 많은 사람에게 꼭 추천해주고 싶은 문제이다. 이 문제를 오류없이 한 번에 풀 수 있을 정도가 된다면 구현 문제에 자신을 가져도 좋을 것이다.
끝으로 전체 소스코드를 남긴다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Growth {
int row;
int col;
int time;
int color;
Growth(int _row, int _col, int _time, int _color) :row(_row), col(_col), time(_time), color(_color) {}
};
int N, M, G, R, ans, tmp;
pair<int,int> garden[51][51];
int used[2501];
int used2[2501];
int dirR[4] = { 0,1,0,-1 };
int dirC[4] = { 1,0,-1,0 };
vector<int>g_pos;
vector<int>r_pos;
vector<int>pos;
vector<pair<int, int>>soil;
void solve(int index);
void solve2(int index);
int simulation();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> tmp;
garden[i][j] = { tmp,0 };
if (tmp == 2)
{
soil.push_back({ i,j });
}
}
}
solve(0);
cout << ans;
return 0;
}
void solve(int index)
{
if (index==G+R)
{
solve2(0);
}
if (index < G+R)
{
for (int i = 0; i < soil.size(); i++)
{
if (used[i] == 0)
{
if (!pos.empty() && pos.back() > i)
{
continue;
}
pos.push_back(i);
used[i] = 1;
solve(index + 1);
pos.pop_back();
used[i] = 0;
}
}
}
}
void solve2(int index)
{
if (index == G)
{
for (int i = 0; i < pos.size(); i++)
{
if (used2[i] == 0)
{
r_pos.push_back(pos[i]);
}
}
tmp = simulation();
r_pos.clear();
if (ans < tmp)
{
ans = tmp;
}
return;
}
if (index < G)
{
for (int i = 0; i < pos.size(); i++)
{
if (used2[i] == 0)
{
if (!g_pos.empty() && g_pos.back() > pos[i])
{
continue;
}
g_pos.push_back(pos[i]);
used2[i] = 1;
solve2(index + 1);
g_pos.pop_back();
used2[i] = 0;
}
}
}
}
int simulation()
{
int ret = 0;
pair<int,int> _garden[51][51];
queue<Growth>q;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
_garden[i][j] = { garden[i][j].first,garden[i][j].second };
}
}
for (int i = 0; i < G; i++)
{
garden[soil[g_pos[i]].first][soil[g_pos[i]].second] = { 3,0 };
q.push(Growth(soil[g_pos[i]].first, soil[g_pos[i]].second, 0, 3));
}
for (int i = 0; i < R; i++)
{
garden[soil[r_pos[i]].first][soil[r_pos[i]].second] = { 4,0 };
q.push(Growth(soil[r_pos[i]].first, soil[r_pos[i]].second, 0, 4));
}
//0 : 호수, 1 : 배양액을 뿌릴 수 없는 땅, 2 : 배양액을 뿌릴 수 있는 땅
//3 : 초록색 배양액을 뿌린 땅, 4 : 빨간색 배양액을 뿌린 땅 5 : 꽃이 핀 땅
while (!q.empty())
{
Growth growth = q.front();
q.pop();
if (garden[growth.row][growth.col].first == 5)
{
continue;
}
for (int i = 0; i < 4; i++)
{
int nR = growth.row + dirR[i];
int nC = growth.col + dirC[i];
if(nR>=0 && nR<N && nC>=0 &&nC<M)
{
if (garden[nR][nC].first > 0 && garden[nR][nC].first < 3)
{
garden[nR][nC].first = growth.color;
garden[nR][nC].second = growth.time + 1;
q.push(Growth(nR, nC, growth.time + 1, growth.color));
}
if (growth.color == 4)
{
if (garden[nR][nC].first == 3 && garden[nR][nC].second == growth.time + 1)
{
garden[nR][nC].first = 5;
ret++;
}
}
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
garden[i][j] = { _garden[i][j].first, _garden[i][j].second };
}
}
return ret;
}