백준 17135 - 캐슬 디펜스(C++, 복습)

문제 링크입니다 https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

삼성 SW 문제였습니다. 구현하는 것이 많았던만큼, 신경을 써야했던 문제였습니다.

 

문제 조건

출력 예시

 

문제 접근 방법

1. 궁수 3명을 DFS를 통해서 순차적으로 선택한다.

2. map을 확인하면서 적이 남아있는지를 확인한다.

3. 적이 남아 있다면, 궁수와의 거리를 측정해, 쏠 수 있는지의 여부를 정한다.

4. 적을 이동한다.

5. 적이 없어질때까지 반복한뒤, 죽인 적의 수를 최댓값과 비교한다.

 

 

문제 접근 방법 - 1번

void select_archer(int start, int cnt) {
    if (cnt == 3) {
        kill = 0;
        get_rid_of();
        answer = max(answer, kill);
        return;
    }   
    for (int i = start; i <= M; i++) {
        if (!Select[i]) {
            Select[i] = true;
            archer_spot.push_back(i);
            select_archer(i, cnt + 1);
            archer_spot.pop_back();
            Select[i] = false;
        }
    }
}

함수의 For문을 통해서 순서대로 3명을 선택합니다.

(1번 + 2번 + 5번) 이나 (5번 + 2번 + 1번)은 결과적으로는 같은 값을 가져오기에 1번부터 뽑는 것이 핵심입니다.

뽑은 궁수가 3명이 되면, 현재 궁수의 위치를 바탕으로 적을 소탕하러 갑니다.

 

 

문제 접근 방법 - 2번

bool find_enemy() {
    bool flag = true;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 1) {
                flag = false;
                enemy.push_back(make_pair(i, j));
            }
        }
    }
    return flag;
}

적이 한명이라도 존재한다면, 죽일 수 있는지의 여부를 확인해야하기에 false를 return 한뒤, 적의 위치를 백터에 저장했습니다.

 

 

문제 접근 방법 - 3번

int get_distance(int start, int x, int y) {
    return abs(N + 1 - x) + abs(start - y);
}

bool cmp(ene a, ene b) {
    if (a.dis < b.dis) return true;
    else if (a.dis == b.dis) {
        if (a.y < b.y) return true;
        return false;
    }
    return false;
}

void shot_enemy() {
    vector<pair<int, int>> enemy_can_kill;
    for (int i = 0; i < archer_spot.size(); i++) {
        vector<ene> can_kill;
        for (int j = 0; j < enemy.size(); j++) {
            int distance = get_distance(archer_spot[i], enemy[j].first, enemy[j].second);
            if (distance <= D) {
                can_kill.push_back({ enemy[j].first, enemy[j].second, distance });
            }
        }
        if (can_kill.size() > 1) {
            sort(can_kill.begin(), can_kill.end(), cmp);
            enemy_can_kill.push_back(make_pair(can_kill[0].x, can_kill[0].y));
        }
        else if (can_kill.size() == 1) {
            enemy_can_kill.push_back(make_pair(can_kill[0].x, can_kill[0].y));
        }
        else {
            enemy_can_kill.push_back(make_pair(0,0));
        }
    }
    for (int i = 0; i < enemy_can_kill.size(); i++) {
        int xx = enemy_can_kill[i].first;
        int yy = enemy_can_kill[i].second;
        if (xx == 0 && yy == 0) continue;
        if (check[xx][yy] == 0) {
            check[xx][yy] = 1;
            map[xx][yy] = 0;
            kill++;
        }
    }
}

 

이 문제의 핵심 코드입니다.

1번 궁수부터 3번 궁수까지 모든 적과의 위치를 확인합니다.

거리가 D이하인 경우, 섬멸할 수 있는 적이기에, 백터에 저장합니다. 그 후에, 백터에 저장된 적들의 수대로 나눕니다.

1. 잡을 수 있는 적이 2명 이상인 경우 -> 1. 거리 + 2. y좌표의 순서대로 정렬 뒤, 맨 처음 적을 죽입니다.

2. 잡을 수 있는 적이 1명인 경우 -> 해당 적을 죽입니다.

3. 잡을 수 있는 적이 없을 경우 -> 무효 표시를 합니다.

해당 과정을 거친 뒤, 잡을 수 있는 적들을 잡았다고 표시합니다. 

이때 check[][] 배열의 역할이 중요한데, 다수의 궁수가 한명의 적을 동시에 공격할 수 있습니다. 이때 중복으로 잡은 횟수가 올라가는 것을 방지하기 위해, check[][]배열을 이용했습니다.

 

 

문제 접근 방법 - 4번

 for (int i = enemy.size() - 1; i >= 0; i--) {
            int xx = enemy[i].first;
            int yy = enemy[i].second;
            if (map[xx][yy] == 0) continue;
            if (xx == N) {
                map[xx][yy] = 0;
            }
            else {
                map[xx][yy] = 0;
                map[xx + 1][yy] = 1;
            }
        }

적들을 소탕한 후에, map[][]배열의 값이 1이라면 아직 적이 있다는 의미입니다. 그때 이 적들을 옮겨줍니다.

행의 가장 아래 적들부터 옮겨주는 것이 핵심입니다 -> 위에서 부터 이동한다면, 이미 죽은 적들을 살았다고 표시할 수 있기 때문입니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int N, M, D, kill, answer;
int archer[16][16];
int map[16][16];
int check[16][16];
bool Select[16];
vector<int> archer_spot;
vector<pair<int, int>> enemy;
typedef struct ene {
    int x;
    int y;
    int dis;
}ene;

bool find_enemy() {
    bool flag = true;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 1) {
                flag = false;
                enemy.push_back(make_pair(i, j));
            }
        }
    }
    return flag;
}

int get_distance(int start, int x, int y) {
    return abs(N + 1 - x) + abs(start - y);
}

bool cmp(ene a, ene b) {
    if (a.dis < b.dis) return true;
    else if (a.dis == b.dis) {
        if (a.y < b.y) return true;
        return false;
    }
    return false;
}

void shot_enemy() {
    vector<pair<int, int>> enemy_can_kill;
    for (int i = 0; i < archer_spot.size(); i++) {
        vector<ene> can_kill;
        for (int j = 0; j < enemy.size(); j++) {
            int distance = get_distance(archer_spot[i], enemy[j].first, enemy[j].second);
            if (distance <= D) {
                can_kill.push_back({ enemy[j].first, enemy[j].second, distance });
            }
        }
        if (can_kill.size() > 1) {
            sort(can_kill.begin(), can_kill.end(), cmp);
            enemy_can_kill.push_back(make_pair(can_kill[0].x, can_kill[0].y));
        }
        else if (can_kill.size() == 1) {
            enemy_can_kill.push_back(make_pair(can_kill[0].x, can_kill[0].y));
        }
        else {
            enemy_can_kill.push_back(make_pair(0,0));
        }
    }
    for (int i = 0; i < enemy_can_kill.size(); i++) {
        int xx = enemy_can_kill[i].first;
        int yy = enemy_can_kill[i].second;
        if (xx == 0 && yy == 0) continue;
        if (check[xx][yy] == 0) {
            check[xx][yy] = 1;
            map[xx][yy] = 0;
            kill++;
        }
    }
}


void get_rid_of() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            map[i][j] = archer[i][j];
        }
    }
    while (1) {
        enemy.clear();
        memset(check, 0, sizeof(check));
        if (find_enemy()) break;
        shot_enemy();
        for (int i = enemy.size() - 1; i >= 0; i--) {
            int xx = enemy[i].first;
            int yy = enemy[i].second;
            if (map[xx][yy] == 0) continue;
            if (xx == N) {
                map[xx][yy] = 0;
            }
            else {
                map[xx][yy] = 0;
                map[xx + 1][yy] = 1;
            }
        }
    }
}

void select_archer(int start, int cnt) {
    if (cnt == 3) {
        kill = 0;
        get_rid_of();
      //  cout << kill << "\n";
        answer = max(answer, kill);
        return;
    }   
    for (int i = start; i <= M; i++) {
        if (!Select[i]) {
            Select[i] = true;
            archer_spot.push_back(i);
            select_archer(i, cnt + 1);
            archer_spot.pop_back();
            Select[i] = false;
        }
    }
}

void solve() {
    select_archer(1,0);
    cout << answer;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> D;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> archer[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!