[BOJ] 캐슬디펜스

[문제]

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

17135번: 캐슬 디펜스

[풀이]

 

17135

맞았습니다!!

1988 KB

4 ms

C++14 / 수정

2720 B

 

1) 생각보다 까다로운..? 문제였다. 

 

2) 최대로 죽일 수 있는 적 = 다른 궁수가 찜하지 않는 적 중에 D거리 이하에 있는 적이라 생각하여 다른 궁수가 찜한 적은 map[][] = 2로 표시를 했다.

 

3) 궁수는 총 3명이 배치될 수 있다. (dfs로 조합 생성)

 

4) 선택된 궁수를 가지고 적을 죽이러 가야한다. 나는 적이 내려오나, 궁수가 올라가나 똑같다고 생각해서 그냥 궁수를 올렸다. 

 

5) 궁수를 올릴 경우 n을 역순으로 돌려주면 된다. 

 

6) 궁수는 총 3방향에 있는 적을 탐색하고 죽일 수 있으므로 3방향만 살핀다. (좌, 상, 우) 

죽일 수 있는 적이 여러 명인 경우 가장 왼쪽에 있는 적을 선택하기 때문에 왼쪽 기준으로 오른쪽 방향으로 정의해야 한다. (안그럼 28%에서 실패함 ;-0 )

 

7) killEnemies() 에는 n부터 감소하는 x좌표와 궁수가 있는 y좌표가 파라미터로 넘어간다. 

• map[x-1][y] == 2 (다른 궁수가 찜한 적) 이면 죽이지 않기 때문에 0을 리턴한다. 

• map[x-1][y] == 1 이면 내가 죽일 수 있는 적이기 때문에 적의 좌표를 저장하는 좌표를 저장하고 좌표에 적힌 값을 2로 바꾼다.

• 그 외에 값이 따로 없다면 큐를 만들고 3방향으로 탐색을 한다. 

• dist는 궁수가 탐색할 수 있는 거리를 저장하고 이 수가 d보다 커지면 더 이상 탐색하지 않는다.

8) 좋은 테스트 케이스 [디버깅용]

5 5 2

1 0 1 1 1

0 1 1 1 1

1 0 1 0 1

1 1 0 1 0

1 0 1 0 1

 

답: 14

---

 

//캐슬디펜스
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
typedef pair<int, int> pp;
typedef pair<int, pp> ipp;
 
vector<pp> enemy;
int n, m, d, ans = 0;
int map[16][16];
bool picked[16];
 
vector<pp> dieEnemy;
 
int dx[3] = {0, -1, 0}, dy[3] = {-1, 0, 1}; //상 좌 우 (하는 볼 필요 없음 (밑에서부터 치고 올라가기 때문에))
 
int doKill(int x, int y)
{
    if (map[x][y] == 2)
        return 0;
    if (map[x][y] == 1)
    {
        //현재 좌표에 적이 있다면
        map[x][y] = 2;
        //죽은 적은 die에 넣는다.
        dieEnemy.push_back(pp(x, y));
        return 1;
    }
 
    //d만큼의 거리 안에 적이 있는지 없는지 확인한다.
    queue<ipp> q;
    q.push(ipp(1,pp(x, y))); //dist, x, y
 
    bool visited[16][16] = {{0}};
 
    visited[x][y] = true;
 
    while(!q.empty()) {
        int cx = q.front().second.first;
        int cy = q.front().second.second;
        int dist = q.front().first;
        q.pop();
 
        if (dist + 1 > d) continue; //한계범위를 넘음 
 
        for (int i = 0; i < 3; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
 
            if (nx < 0 || ny < 0 || ny >= m || visited[nx][ny]) continue;
 
            if (map[nx][ny] == 2) {
                return 0;
            }
            else if (map[nx][ny]== 1) {
                dieEnemy.push_back(pp(nx, ny));
                map[nx][ny] = 2;
                return 1;
            }
 
            visited[nx][ny] = true;
            q.push(ipp(dist+1, pp(nx, ny)));
        }
    }
    return 0;
}
int killEnemy()
{
    //d거리 이하에 있는 적을 공격할 수 있다.
    int ret = 0;
    int idx = 0;
    int attacker[3];
    for (int i = 0; i < m; i++)
    {
        if (picked[i])
        {
            //한 궁수가 있는 위치
            attacker[idx++] = i;
        }
    }
 
    int tmp = n;
    while (tmp > 0) //총 n번의 기회
    {
        dieEnemy.clear();
        for (int i = 0; i < 3; i++)
        {
            ret += doKill(tmp-1, attacker[i]);
        }
        
 
        for (auto j : dieEnemy)
        {
            map[j.first][j.second] = 0;
        }
 
        tmp--;
    }
 
    return ret;
}
void dfs(int idx, int cnt)
{
    if (cnt == 3)
    {
        //궁수 다 뽑음
        int c_map[16][16];
 
        memcpy(c_map, map, sizeof(map));
 
        ans = max(ans, killEnemy());
 
        memcpy(map, c_map, sizeof(map));
 
        return;
    }
 
    if (idx > m) return;
 
    for (int i = idx; i < m; i++)
    {
        if (!picked[i])
        {
            picked[i] = true;
            dfs(i+1, cnt + 1);
            picked[i] = false;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    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]; //1은 적, 0은 빈칸
        }
    }
 
    dfs(0, 0);
    cout << ans << '\n';
    return 0;
}