[BOJ] 17135 : 캐슬 디펜스

17135 : 캐슬 디펜스

풀이

조합+BFS

삼성19-4월 SW상시테스트 1번문제

시험장에서 50분만에 푼 문제이다.

복원문제도 똑같이 바로 풀었다.

dx,dy를 이렇게 설정해두면, 우선순위를 정할 필요가 없다.

항상 왼쪽, 위, 오른쪽 순서로 큐에 넣으면 된다.

시험장에선 target이 없을 수도 있는데, i<3을 해서 런타임에러가 나서 잠깐 식은땀을 흘렸었다.

i<target.size()로 바꿔서 해결했다.

푸는 순서는 이렇다.

1.궁수 포지션을 정해준다 (조합)

2.3~5을 반복한다, arr에 1이 없으면 반복 종료.

3.각각 궁수가 쏜다(shot- bfs로 구현)-타겟:target에 포지션 저장

4.target을 없앤다( 이때 중복된 적은 카운트하면 안된다 )

5.적들이 전진한다(move)

6.이번에 더많이맞췄으면 정답갱신

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m, d;
int ans;
vector<int> position;
vector<pair<int,int>> target;
int arr[15][15];
int backup[15][15];
int chk[15][15];
const int dx[] = { 0,-1,0 };
const int dy[] = { -1,0,1 };

void shot(int p) {
    memset(chk, 0, sizeof(chk));
    queue<pair<pair<int, int>,int>> q;
    q.push({ {n - 1,p}, 1});
    chk[n - 1][p] = 1;
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        if (cnt > d) {
            break;
        }
        if (arr[x][y] == 1) {
            target.push_back({x,y});
            break;
        }
        for (int dir = 0; dir < 3; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&chk[nx][ny] == 0) {
                q.push({ {nx,ny}, cnt+1 });
                chk[nx][ny] = 1;
            }
        }
    }
}

int move() {
    int num=0;
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            arr[i + 1][j] = arr[i][j];
            if (arr[i + 1][j] == 1) {
                num++;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        arr[0][i] = 0;
    }
    return num;
}

void go(int s,int cnt) {
    if (cnt == 3) {
        memcpy(arr, backup, sizeof(arr));
        int tmp = 0;
        while (1) {
            for (int i = 0; i < 3; i++) {
                shot(position[i]);
            }
            for (int i = 0; i < target.size(); i++) {
                int x = target[i].first;
                int y = target[i].second;
                if (arr[x][y] == 1) {
                    arr[x][y] = 0;
                    tmp++;
                }
            }
            target.clear();
            int num = move();
            if (num == 0) {
                break;
            }
        }
        if (tmp > ans)
            ans = tmp;
        return;
    }


    for (int i = s; i < m; i++) {
        position.push_back(i);
        go(i+1, cnt + 1);
        position.pop_back();
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            backup[i][j] = arr[i][j];
        }
    }
    go(0,0);
    cout << ans;
    return 0;
}

Written on April 8, 2019