https://www.acmicpc.net/problem/17135
이 문제는 그냥 여러개 섞어놓은 문제이다 병사를 배정하는것은 조합으로 dfs로 풀면 되고
병사들이 몬스터를 잡는건 bfs로 풀면된다 조합에대한 모든것을 bfs함으로 브루트포스이기도 하다 사실이문제는 단지 기본적인 알고리즘 여러개를 섞어놓은것이다
주의할 점은 bfs를 할때
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};이 순서대로 해야한다 bfs가 거리가 가까운거는 보장하지만 왼쪽 탐색을 하기위해서는 해당 인덱스를 따라 해야지 왼쪽부터 탐색한다
또한 탐색하자마자 바로 0으로 바꾸지말고 중복으로 한 몬스터를 때릴수 있으므로 4로 체크하고 이후에 0으로 바꾼다
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int originArr[16][15];
int copyArr[16][15];
int N, M, D;
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};
int maxNum;
bool isVisited[16][15] = { 0, };
bool AllDie() {
bool isDie = true;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copyArr[i][j] == 1)
isDie = false;
}
}
return isDie;
}
void CopyOrigin() {
for (int i = 0; i <= N; i++) {
for (int j = 0; j < M; j++) {
copyArr[i][j] = originArr[i][j];
}
}
}
bool CanGo(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < M ) {
return true;
}
else {
return false;
}
}
void downEnemy() {
for (int i = N-1 ; i > 0; i--) {
for (int j = 0; j < M; j++) {
copyArr[i][j] = copyArr[i - 1][j];
if (copyArr[i][j] == 4)
copyArr[i][j] = 0;
}
}
for (int i = 0; i < M; i++) {
copyArr[0][i] = 0;
}
}
int bfs(int armyX, int armyY) {
queue<pair<int, pair<int, int>>> ArmyQ;
ArmyQ.push({ 0,{armyX,armyY} });
int count = 0;
while (!ArmyQ.empty()) {
int curX = ArmyQ.front().second.first;
int curY = ArmyQ.front().second.second;
int cost = ArmyQ.front().first;
ArmyQ.pop();
if (cost > D)
break;
if (copyArr[curX][curY] == 4) {
break;
}
if (copyArr[curX][curY] == 1) {
copyArr[curX][curY] = 4;
count += 1;
break;
}
for (int i = 0; i < 3; i++) {
int nextX = curX + goX[i];
int nextY = curY + goY[i];
if (CanGo(nextX, nextY)) {
ArmyQ.push({ cost + 1,{nextX,nextY} });
}
}
}
return count;
}
void dfs(int start, int count) {
if (count == 3) {// 병사를 3명 다배치 했을 경우
CopyOrigin();
int num = 0;
while (!AllDie()) {
for (int i = 0; i < M; i++) {
if (copyArr[N][i] == 3) {
num += bfs(N, i);
}
}
downEnemy();
}
maxNum = max(num, maxNum);
}
else {
for (int i = start+1; i < M; i++) {
originArr[N][i] = 3;
dfs(i, count + 1);
originArr[N][i] = 2;
}
}
}
int main() {
cin >> N >> M >> D;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> originArr[i][j];
}
}
for (int i = 0; i < M; i++) {
originArr[N][i] = 2;
}
for (int i = 0; i < M; i++) {
originArr[N][i] = 3;
dfs(i, 1);
originArr[N][i] = 2;
}
cout << maxNum;
}