백준[17135] 캐슬 디펜스

이 문제의 출처는 아래와 같다.

 

https://www.acmicpc.net/problem/17135

 

'삼성 A형 기출문제' 문제집에 있는 문제이다. 

 

우선 필자는 단순히 구현했다. N,M 의 범위가 작기 때문에 모든 경우를 for 반복문으로 돌려 문제에서 주어진 조건에 맞게 구현하였다.

 

3명의 궁수를 3중 for문으로 모든 경우에 위치시키고 각 궁수마다 적의 (x좌표, y좌표, 궁수와의 거리)  가지도록 하는 구조체를 사용해 2차원 map에서 적을 만나는 경우 각 궁수별로 해당 적까지의 거리와 위치를 vector에 저장하였다. 

 

해당 벡터들의 크기가 1보다 크다는 뜻은 여러 적을 죽일 수 있으다는 뜻이고 문제의 조건에 맞게 거리가 가장 가깝고 제일 왼쪽에 있는 적을 제거하도록 벡터를 정렬하여 적을 줄여나갔다.

 

이후, 적이 있는지 없는지 판별하고 있다면 한줄씩 내리고 위 과정을 반복한다.

 

* 다른 풀이로는 queue를 사용하여 BFS로 해결하는 방법도 있지만, 필자는 해당 방법이 떠오르지 않아 위 과정을 통해 해결하였다.

또한, main에서 궁수의 위치를 행으로 조절하는 오류로 해결하는데 시간이 걸렸다.*'

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
#include<map>
 
using namespace std;
 
struct info {
    int xx = 0, yy = 0, DD = 0;
};
 
bool cmp(info a, info b) {
    if (a.DD == b.DD) {
        return a.yy < b.yy;
    }
    else return a.DD < b.DD;
}
 
int n, m,d, arr[21][21],ans,num,Map[21][21];
 
void init() {
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < m; b++) {
            arr[a][b] = Map[a][b];
        }
    }
}
 
int Ar() 
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1) {
                return 0;
            }
        }
    }
    return 1;
}
 
void down()
{    
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (i == n-1 && arr[i][j] == 1) arr[i][j] = 0;
            else if (arr[i][j] == 1) swap(arr[i][j], arr[i + 1][j]);
        }
    }
    
}
 
void cal(int x1,int x2,int x3,int N) {
    vector<info> v[3];
    info val;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1) {
                if (abs(N - i) + abs(x1 - j) <= d) {
                    val.xx = i, val.yy = j, val.DD = abs(N - i) + abs(x1 - j);
                    v[0].push_back(val);
                }
                if (abs(N - i) + abs(x2 - j) <= d) {
                    val.xx = i, val.yy = j, val.DD = abs(N - i) + abs(x2 - j);
                    v[1].push_back(val);
                }
                if (abs(N - i) + abs(x3 - j) <= d) {
                    val.xx = i, val.yy = j, val.DD = abs(N - i) + abs(x3 - j);
                    v[2].push_back(val);
                }
            }
        }
    }
    if (v[0].size() != 0) {
        sort(v[0].begin(), v[0].end(),cmp);
        if (arr[v[0][0].xx][v[0][0].yy] == 1) num++;
        arr[v[0][0].xx][v[0][0].yy] = 0;
 
    }
    if (v[1].size() != 0) {
        sort(v[1].begin(), v[1].end(),cmp);
        if (arr[v[1][0].xx][v[1][0].yy] == 1) num++;
        arr[v[1][0].xx][v[1][0].yy] = 0;
    }
    if (v[2].size() != 0) {
        sort(v[2].begin(), v[2].end(),cmp);
        if (arr[v[2][0].xx][v[2][0].yy] == 1) num++;
        arr[v[2][0].xx][v[2][0].yy] = 0;
    }
    if (Ar() == 0) {
        down();
        cal(x1, x2, x3, N);
    }
    else return;
    
}
 
int main()
{
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            Map[i][j] = arr[i][j];
        }
    }
    for (int i = 0; i < m - 2; i++) {
        for (int j = i + 1; j < m - 1; j++) {
            for (int z = j + 1; z < m; z++) {
 
                cal(i, j, z, n);
                init();
                //cout << num << endl;
                ans = max(ans, num);
                num = 0;
            }
        }
    }
    printf("%d", ans);
    return 0;
}