https://www.acmicpc.net/problem/17135
까다로운 문제입니다.
-
궁수위치 선정
-
궁수 사정거리 안에 들어오는 적 사살
2-1. 같은 사정거리라면 제일 왼쪽
2-2. 동시에 두명한테 맞았다면 한명한테만 kill로
- 적 한칸씩 전진
이 경우를 잘 고려해주시면 됩니다. 특히 2번의 경우에서 많은 실수가 나오니
유의해주셔야합니다.
저 같은 경우, 궁수 위치 선정은 dfs방식을 응용해서 완탐을 해줬고,
2번은 BFS를 사용하였습니다. bfs돌리면서 적을 죽였으면 바로 계산하지 않고
(2명이상의 궁수가 떄릴수있기때문)
배열에 넣어둔 후 bfs가 끝나면 그 때 판단해줬습니다.
이 후 적 내려오는 건 반복문을 통해 구현했고 적이 없으면 return 시켰습니다.
2차
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//1125
int n, m, d, map[16][16], result;
int orimap[16][16];
int archerP[3];
queue < pair <int, int> > q;
struct Enemy {
int x;
int y;
};
int dx[] = { -1,0,0 };
int dy[] = { 0,-1,1 };
vector < pair <int, int>> v;
bool enemyMove() {
bool notEnemy = true;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (map[i][j]) {
if (i == n - 1)map[i][j] = 0;
else {
notEnemy = false;
map[i][j] = 0;
map[i + 1][j] = 1;
}
}
}
}
return notEnemy;
}
void bfs(int archerPosittion) {
bool ch[16][16] = { 0, };
ch[n - 1][archerP[archerPosittion]] = true;
q.push(make_pair(n - 1, archerP[archerPosittion]));
Enemy enemy;
enemy.y = 2e9;
bool attacked = false;
int dist = 0;
while (!q.empty()) {
dist++;
int size = q.size();
if (attacked) {
while (!q.empty()) q.pop();
break;
}
for (int t = 0; t < size; t++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (map[x][y] == 1) {//사정거리내 적
attacked = true;
if (enemy.y > y) {
enemy.x = x;
enemy.y = y;
}
}
if (attacked) continue;//더이상 공격범위넓히기 ㄴㄴ
if (dist == d)continue;//공격범위 초과해도 ㄴㄴ
for (int i = 0; i < 3; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && ny < m && !ch[nx][ny]) {
q.push(make_pair(nx, ny));
ch[nx][ny] = true;
}
}
}
}
if (enemy.y != 2e9) v.push_back(make_pair(enemy.x, enemy.y));
}
void dfs(int sx, int cnt) {
if (cnt == 3) {
int killCnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = orimap[i][j];
}
}
while (1) {
v.clear();
for (int i = 0; i < 3; i++) bfs(i);//공격할 적 설정
for (int i = 0; i < v.size(); i++) {//kill
if (map[v[i].first][v[i].second] != 0) {
map[v[i].first][v[i].second] = 0;
killCnt++;
}
}
if (enemyMove()) break;//적 내려옴(아무도없으면 break)
}
result = result > killCnt ? result : killCnt;
return;
}
for (int i = sx; i < m; i++) {
archerP[cnt] = i;
dfs(i + 1, cnt + 1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
orimap[i][j] = map[i][j];
}
}
dfs(0, 0);
cout << result;
}
1차
#include <iostream>
#include <queue>
using namespace std;
int n, m, d, result;
int map[16][16];
int orimap[16][16];
struct Info {
int x;
int y;
};
bool archerLoc[16];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int bfs() {
int kill = 0;
while (1) {
queue <Info> q[3];
bool ch[3][16][16] = { 0, };
bool attack[3] = { 0, };
Info attacked[3];
int temp = 0;
for (int i = 0; i < m; i++) {
if (archerLoc[i]) {//처음 궁수 위치 큐에넣음(bfs위해)
q[temp].push({ n,i });
ch[temp][n][i] = true;
temp++;
}
}
for (int p = 0; p < 3; p++) {
int range = 0;//사정거리
while (!q[p].empty()) {
if (attack[p])break;//이미 적을 죽였다면 break
range++;
int size = q[p].size();//큐 사이즈만큼만 돌려서 같은 사정거리끼리 계산
for (int i = 0; i < size; i++) {
int x = q[p].front().x;
int y = q[p].front().y;
q[p].pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n&&ny < m&&ch[p][nx][ny] == false
&& range <= d) {
if (map[nx][ny] == 1) {//bfs돌리는 중 적을 발견시
if (attack[p]) {//같은 사정거리 내에서 중복 발견
if (attacked[p].y > ny) {//왼쪽
attacked[p].x = nx;
attacked[p].y = ny;
}
}
else {//처음발견
attack[p] = true;
attacked[p].x = nx;
attacked[p].y = ny;
}
}
else {
if (!attack[p]) {//아무도 못죽였을시
ch[p][nx][ny] = true;
q[p].push({ nx,ny });
}
}
}
}
}
}
}
for (int i = 0; i < 3; i++) {
if (attack[i]) {//죽였던 녀석들 판단(궁수 2명이상이 한녀석을 죽였을때를위해
int x = attacked[i].x;
int y = attacked[i].y;
if (map[x][y] != 0) {//다른궁수가 안때린애라면
kill++;
map[x][y] = 0;//0으로해서 죽음 표시
}
}
}
bool end = true;
for (int i = n - 1; i >= 0; i--) {//밑에부터 돌린다
for (int j = 0; j < m; j++) {
if (map[i][j]) {
end = false;
map[i][j] = 0;
if (i + 1 < n) map[i + 1][j] = 1;//제일 밑인경우 그냥 사라짐
}
}
}
if (end) break;//반복문다돌았는데 아무도 없었으면 break;
}
return kill;
}
void dfs(int loc, int cnt) {//궁수위치선정
if (cnt == 3) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
map[i][j] = orimap[i][j];
int kill = bfs();//위치선정 후 BFS를이용해서 공격
result = result >= kill ? result : kill;
return;
}
for (int i = loc; i < m; i++) {
archerLoc[i] = true;
dfs(i + 1, cnt + 1);
archerLoc[i] = false;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
orimap[i][j] = map[i][j];
}
}
dfs(0, 0);
cout << result;
}
- 나 혼자 말하고 나 혼자 듣는 말
서울대에서 풀었을 땐 2시간 반 걸려서 겨우 풀었던 문제….