17135번: 캐슬 디펜스 (백준 온라인 저지, C++)

문제 풀이

 

 문제 해결을 위한 절차는 다음과 같습니다.

1) 궁수의 위치를 정하여 simulation 함수로 넘겨줍니다.

2) 궁수마다 가장 가까운 적의 위치를 중복없이 저장해 줍니다.

3) 사정 거리 내에 들어온다면 적을 없애주고, 적을 한 칸 전진 시킵니다.

4) 남아있는 적이 없다면 simulation을 종료시키고 물리친 적이 가장 많을 때를 저장시켜 줍니다.

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
 
using namespace std;
 
int n, m, d;
int field[15][15];
 
int dist(int ex, int ey, int ay) {
    return abs(n - ex) + abs(ey - ay);
}
 
int simulation(int a, int b, int c) {
    
    int sum = 0;
    int tmp[15][15];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = field[i][j];
        }
    }
 
    while (1) {
        vector<int> v = { a, b, c };
        set<pair<int, int>> s;
 
        for (auto x : v) { //x = a
            
            int dist_f[15][15];
            int dist_min = -1;
 
            memset(dist_f, -1, sizeof(dist_f));
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    
                    if (tmp[i][j] == 1) {
                        dist_f[i][j] = dist(i, j, x);
                        if (dist_min == -1 || dist_min > dist_f[i][j]) {
                            dist_min = dist_f[i][j];
                        }
                    }
                }
            }
 
            if (dist_min <= d) {
 
                int ex = -1, ey = -1;
                for (int j = 0; j < m; j++) {
                    for (int i = 0; i < n; i++) {
                        if (dist_min == dist_f[i][j]) {
                            ex = i;
                            ey = j;
                            break;
                        }
                    }
                    if (ey != -1) {
                        break;
                    }
                }
                s.emplace(ex, ey);
            }
        }
        
        for (auto x : s) {
            tmp[x.first][x.second] = 0;
            sum++;
        }
        
        bool isFin = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if(i == 0){
                    tmp[i][j] = 0;
                }
                else{
                    tmp[i][j] = tmp[i - 1][j];
                }
                
                if (tmp[i][j] == 1) {
                    isFin = false;
                }
            }
        }
        if (isFin) return sum;
    }
}
 
int main() {
 
    cin >> n >> m >> d;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> field[i][j];
        }
    }
 
    vector<int> p(m, 0);
    p[0] = 1;
    p[1] = 1;
    p[2] = 1;
 
    sort(p.begin(), p.end());
 
    int ans = -1;
    do{
        vector<int> v;
 
        for (int i = 0; i < m; i++) {
            if (p[i] == 1) {
                v.push_back(i);
            }
        }
        int sum = simulation(v[0], v[1], v[2]);
 
        if (ans == -1 || sum > ans) {
            ans = sum;
        }
 
    } while (next_permutation(p.begin(), p.end()));
 
    cout << ans << '\n';
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

17135번: 캐슬 디펜스