[ 백준-17135번 / 완전탐색 ] 캐슬 디펜스 (삼성SW)

1. 문제

---

 

17135번: 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

예제 입력 1 복사

5 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1

예제 출력 1 복사

3

 

 

 

 

 

2. 소스코드

---

1회차

 

- 생각보다 구현을 매우 매우 못했던 문제.

1. 궁수가 적을 찾는 걸 bfs로 구현하지 않음.

2. 이 때문에 예외가 발생하였고, 빨리 찾지 못함.

3. DFS가 미숙해 중복 없이 구현하지 못함.

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n, m, range, ans, enemyNum;
int map[15][15];
int acherPos[15];

int isInRange(int nx, int ny, int x, int y) {
    int ax = nx - x;
    if (ax < 0) ax *= -1;
    int ay = ny - y;
    if (ay < 0) ay *= -1;

    return ax + ay;
}

pair<int, int> findEnemy(int copyMap[][15], int nx, int ny) {
    //for문을 돌려서 확인하자.
    pair<int, int> pos = { -1,-1 };
    int min = range + 1;
    for (int i = n - 1; i >= n - range; --i) {// range 내에
        for (int j = 0; j < m; ++j) {
            if (copyMap[i][j]) {//적을 찾은경우
                int temp = isInRange(nx, ny, i, j);
                if (temp == min and temp <= range) {
                    if (pos.first != i and pos.second > j) { // 더 아래에 있으면 같아도 바꾼다.
                        pos.first = i;
                        pos.second = j;
                    }
                }
                if (temp < min) {
                    min = temp;
                    pos.first = i;
                    pos.second = j;
                }
            }
        }
    }
    return pos;
}

int findMaxKill() {
    int copyMap[15][15];
    int kill = 0;
    memcpy(copyMap, map, sizeof(copyMap));
    while (true)
    {
        queue <pair<int, int>> shotPos;
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            if (acherPos[i] == 1) { 
                shotPos.push(findEnemy(copyMap, n, i)); // 궁수위치 col값은 n으로 고정
                ++cnt;
                if (cnt == 3) break;// 궁수위치3개다 파악했으면 out
            }
        }//위치를 다구했음
        while (!shotPos.empty()) {// shot!
            auto k = shotPos.front();
            shotPos.pop();
            if (k.first == -1) continue;//못찾은경우 스킵
            if (copyMap[k.first][k.second] == 1) { // 죽이고 킬++
                copyMap[k.first][k.second] = 0;
                ++kill;
            }// 중복으로 쏘는 경우는 자동 continue;
        }
        //모두 죽임
        if (enemyNum == kill) return kill;

        //아니면 한칸씩 내려야함
        bool exist = false;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < m; ++j) {
                if (copyMap[i][j] == 1) {
                    if (i + 1 == n) {//닿은경우
                        copyMap[i][j] = 0; // 사라짐
                        continue;
                    }
                    copyMap[i + 1][j] = copyMap[i][j];
                    copyMap[i][j] = 0;
                    exist = true;
                }
            }
        }//한칸씩 내리기 끝. 반복 
        if (exist == false) return kill;
    }
}


void dfs(int prev, int cnt) {

    if (cnt >= 3) { 
        int res = findMaxKill();
        if (res > ans) ans = res;
        return;
    }

    for (int i = prev; i < m; ++i) {  
        if (acherPos[i] == 0) {
            acherPos[i] = 1;
            dfs(i, cnt + 1);
            acherPos[i] = 0;
        }
    }
}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> range;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> map[i][j];
            if (map[i][j] == 1) ++enemyNum;
        }
    }

    dfs(0, 0);

    cout << ans << '\n';

    return 0;
}

 

 

2회차

 

- 개선점

1. 궁수가 적을 찾는 걸 bfs로 구현하지 않음.

  bfs를 이용해 구현, 그러나 속도에 유의미한 차이는 없었음

2. 이 때문에 예외가 발생하였고, 빨리 찾지 못함.

  해결.

3. DFS가 미숙해 중복 없이 구현하지 못함.

  해결.

4. 적들이 내려오는게 아닌 궁수가 한 칸씩 위로 움직임. 모든 적을 한 칸씩 이동시키는 대신, 궁수 단 한줄만 이동시키므로 성능향상.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <tuple>

using namespace std;

int n, m, range, ans, enemyNum;
int map[16][15];
int dx[] = { 0,-1,0 }; // 왼 위 오
int dy[] = { -1,0,1 }; //아래로 내려가는 경우는 고려하지않음.

pair<int, int> findEnemy(int copyMap[][15], int ax, int ay) {
 
    int visited[16][15] = { 0, };

    queue<tuple<int, int, int>> que;
    que.push(make_tuple( ax, ay, 1));
    visited[ax][ay] = 1;

    while (!que.empty()) {
        auto k = que.front(); que.pop();
        int x = get<0>(k);
        int y = get<1>(k);
        int depth = get<2>(k);

        for (int i = 0; i < 3; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 or ny < 0 or nx >= ax or ny >= m) continue;
            if (visited[nx][ny] or depth > range) continue;

            visited[nx][ny] = 1;
            que.push(make_tuple(nx, ny, depth + 1));
            if (copyMap[nx][ny] == 1) {
                return make_pair(nx, ny);
            }    
        }
    } 
    return make_pair(-1, -1);
}

int findMaxKill() {
    int copyMap[16][15];
    int enemy = enemyNum;
    int kill = 0;
    int acherLine = n;
    memcpy(copyMap, map, sizeof(copyMap));
   
    while (true)
    {
        queue <pair<int, int>> shotPos;
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            if (copyMap[acherLine][i] == 1) {
                shotPos.push(findEnemy(copyMap, acherLine, i));  
                ++cnt;
                if (cnt == 3) break;// 궁수위치3개다 파악했으면 out
            }
        }//위치를 다구했음
        while (!shotPos.empty()) {// shot!
            auto k = shotPos.front();
            shotPos.pop();
            if (k.first == -1) continue;//못찾은경우 스킵
            if (copyMap[k.first][k.second] == 1) { // 죽이고 킬++
                copyMap[k.first][k.second] = 0;
                ++kill;
            }// 중복으로 쏘는 경우는 pass
        }
        //궁수가 전진  
        --acherLine;
        for (int i = 0; i < m; ++i) {
            if (copyMap[acherLine][i] == 1) //기존에 병사가 있던 장소면 
                --enemy;          
            copyMap[acherLine][i] = copyMap[acherLine + 1][i];
        }
        // 모든 적이 사라짐.
        if (enemy == kill) return kill;
    }//end while
}


void dfs(int prev, int cnt) {

    if (cnt >= 3) { 
        int res = findMaxKill();
        if (res > ans) ans = res;
        return;
    }
    for (int i = prev; i < m; ++i) {  
        if (map[n][i] == 0) {
            map[n][i] = 1;
            dfs(i, cnt + 1);
            map[n][i] = 0;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> range;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> map[i][j];
            if (map[i][j] == 1) ++enemyNum;
        }
    }

    dfs(0, 0);

    cout << ans << '\n';

    return 0;
}