1. 문제
설명
길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.
인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.
배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.
아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.
초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.
아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.
배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.
또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.
정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.
입력
첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.
그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.
배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.
출력
첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.
2. 풀이
DFS와 BFS를 같이 사용해서 푸는 꽤나 구현력을 요구하는 문제입니다.
보통 이런 문제는 삼성 코딩 테스트 유형에 많이 나옵니다.
계획1 - 배양액을 뿌릴 수 있는 땅을 G + R개 만큼 고르는 모든 경우의 수 만들기
int slove(int depth, int start) {
if (depth == G + R) return go(0, 0);
int ret = 0;
for (int i = start; i < canSprayLands.size(); i++) {
sprinkledLands[depth] = canSprayLands[i];
ret = max(ret, slove(depth + 1, i + 1));
}
return ret;
}canSprayLands 변수는 배양액을 뿌릴 수 있는 좌표 리스트입니다.
sprinkledLands 변수는 배양액을 뿌릴 수 있는 땅을 G + R개 만큼 고를 때
그 모든 경우의 수를 세팅하는 용도로 사용합니다.
계획2 - 계획1에서 고른 땅에서 G와 R로 나누는 모든 경우의 수 만들기
for (int i = start; i < G + R; i++) {
sprinkledColors[i] = 1;
ret = max(ret, go(depth + 1, i + 1));
sprinkledColors[i] = 0;
}G를 세팅하는 경우만 고르면 R은 자동으로 정해지니까 G만 세팅합니다.
계획3 - BFS로 꽃을 피우는 시뮬레이션을 진행
// G와 R을 나누기
for (int i = 0; i < G + R; i++) {
if (sprinkledColors[i]) {
g.push(sprinkledLands[i]);
simulGarden[sprinkledLands[i].first][sprinkledLands[i].second] = 3;
}
else {
r.push(sprinkledLands[i]);
simulGarden[sprinkledLands[i].first][sprinkledLands[i].second] = 4;
}
}
int ret = 0;
// BFS 시작, 하나라도 empty할 때 종료
while (!g.empty() && !r.empty()) {
// 초록 배양액은 처음에 퍼뜨릴 때 6으로 퍼트리기
while (!g.empty()) {
int y = g.front().first;
int x = g.front().second;
g.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (simulGarden[ny][nx] != 1 && simulGarden[ny][nx] != 2) continue;
tmp.push({ ny, nx });
simulGarden[ny][nx] = 6;
}
}
// 빨강 배양엑 퍼뜨리기
int size = r.size();
while (size--) {
int y = r.front().first;
int x = r.front().second;
r.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (simulGarden[ny][nx] != 1 && simulGarden[ny][nx] != 2 && simulGarden[ny][nx] != 6) continue;
// 초록색 배양액이 퍼뜨러진 경우
if (simulGarden[ny][nx] == 6) {
simulGarden[ny][nx] = 5; // 꽃을 피우고
ret++; // 개수 증가
}
// 일반적으로 퍼지는 경우
else {
simulGarden[ny][nx] = 4;
r.push({ ny, nx });
}
}
}
// tmp -> g로 다시 옮기기
while (!tmp.empty()) {
// 꽃이 된 경우는 제외하고 옮긴다.
if (simulGarden[tmp.front().first][tmp.front().second] == 6) {
// 빨강 배양액이 침범하며 꽃을 피우지 못하게 3으로 전환
simulGarden[tmp.front().first][tmp.front().second] = 3;
g.push(tmp.front());
}
tmp.pop();
}
}이런 식으로 모든 경우의 수를 탐색하며 시뮬레이션 하면 답을 얻을 수 있습니다.
백트래킹, BFS의 꽤 높은 숙달력을 요구하는 문제였습니다.
3. 전체 코드
#define MAX 50
#define FLUID 10
#include <bits/stdc++.h>
using namespace std;
int N, M, G, R;
int garden[MAX][MAX];
int simulGarden[MAX][MAX];
int sprinkledColors[FLUID];
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> canSprayLands;
pair<int, int> sprinkledLands[FLUID];
queue<pair<int, int>> g, r, tmp;
bool isOut(int y, int x) {
return y < 0 || y >= N || x < 0 || x >= M;
}
// 뿌릴 수 있는 땅에서 G와 R로 나누는 모든 경우의 수
int go(int depth, int start) {
if (depth == G) {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
simulGarden[i][j] = garden[i][j];
// G와 R을 나누기
for (int i = 0; i < G + R; i++) {
if (sprinkledColors[i]) {
g.push(sprinkledLands[i]);
simulGarden[sprinkledLands[i].first][sprinkledLands[i].second] = 3;
}
else {
r.push(sprinkledLands[i]);
simulGarden[sprinkledLands[i].first][sprinkledLands[i].second] = 4;
}
}
int ret = 0;
// BFS 시작, 하나라도 empty할 때 종료
while (!g.empty() && !r.empty()) {
// 초록 배양액은 처음에 퍼뜨릴 때 6으로 퍼트리기
while (!g.empty()) {
int y = g.front().first;
int x = g.front().second;
g.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (simulGarden[ny][nx] != 1 && simulGarden[ny][nx] != 2) continue;
tmp.push({ ny, nx });
simulGarden[ny][nx] = 6;
}
}
// 빨강 배양엑 퍼뜨리기
int size = r.size();
while (size--) {
int y = r.front().first;
int x = r.front().second;
r.pop();
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (simulGarden[ny][nx] != 1 && simulGarden[ny][nx] != 2 && simulGarden[ny][nx] != 6) continue;
// 초록색 배양액이 퍼뜨러진 경우
if (simulGarden[ny][nx] == 6) {
simulGarden[ny][nx] = 5; // 꽃을 피우고
ret++; // 개수 증가
}
// 일반적으로 퍼지는 경우
else {
simulGarden[ny][nx] = 4;
r.push({ ny, nx });
}
}
}
// tmp -> g로 다시 옮기기
while (!tmp.empty()) {
// 꽃이 된 경우는 제외하고 옮긴다.
if (simulGarden[tmp.front().first][tmp.front().second] == 6) {
simulGarden[tmp.front().first][tmp.front().second] = 3;
g.push(tmp.front());
}
tmp.pop();
}
}
while (!g.empty()) g.pop();
while (!r.empty()) r.pop();
return ret;
}
int ret = 0;
for (int i = start; i < G + R; i++) {
sprinkledColors[i] = 1;
ret = max(ret, go(depth + 1, i + 1));
sprinkledColors[i] = 0;
}
return ret;
}
// 배양액을 뿌릴 수 있는 땅을 G + R개 만큼 고르는 모든 경우의 수
int slove(int depth, int start) {
if (depth == G + R) return go(0, 0);
int ret = 0;
for (int i = start; i < canSprayLands.size(); i++) {
sprinkledLands[depth] = canSprayLands[i];
ret = max(ret, slove(depth + 1, i + 1));
}
return ret;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> garden[i][j];
if (garden[i][j] == 2) {
canSprayLands.push_back({ i, j });
}
}
}
cout << slove(0, 0);
return 0;
}