[백준] 17135번 : 캐슬 디펜스

문제

 

---

풀이

 

각 턴마다 해야하는 일을 순서대로 써보자.

 

1. 궁수가 적을 타겟팅

2. 동시에 공격

3. 적 이동

 

둘 이상의 궁수가 하나의 적을 공격할 수 있다고 하니 타겟팅만 해두고 한번에 공격해야 한다.

궁수의 공격 범위는 반지름이 d인 반원의 형태라고 볼 수 있는데, 그래서 좌, 상, 우의 순서로 탐색하다 제일 먼저 찾은 적을 공격하면 된다.

 

https://myunji.tistory.com/378

[백준] 16236번 : 아기 상어

가능한 모든 후보를 찾고 정렬했던 이 문제보단 편한 셈이다.

 

동시에 공격하면서 공격한 적의 수를 세면 될 것이고...

적을 이동할 때 판을 그대로 복사해서 아래로 미는 건 좀 비효율적일 것 같다.

그래서 궁수를 이동하기로 했다. 궁수들을 맨 아랫줄부터 한 줄씩 위로 올리면 적이 이동하는 것과 같은 기능을 한다.

 

궁수가 있는 행을 n이라고 하면 0~n-1행까지의 적을 공격할 수 있는 것이니, n이 1보다 크거나 같을때만 탐색한다.

가능한 모든 궁수 배치에 대해 이 과정을 다 해보면서 최댓값을 갱신하면 된다.

---

소스코드

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;

int N, M, D;
vector<vector<int>> board, archer;
pp dir[3] = {{0,  -1}, //좌
             {-1, 0},  //상
             {0,  1}}; //우

void archerPos() {
    for (int i = 0; i < (1 << M); i++) { //비트마스크
        vector<int> tmp;
        for (int j = 0; j < M; j++) {
            if (i & (1 << j))
                tmp.push_back(j);
        }
        if (tmp.size() == 3) //배치된 궁수가 3명이라면
            archer.push_back(tmp);
    }
}

void bfs(int r, int c) {
    vector<vector<int>> dist(N + 1, vector<int>(M, D));
    queue<pp> q;
    dist[r][c] = 0;
    q.push(make_pair(r, c));

    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if (dist[row][col] > D) //더이상 탐색할 필요 없음
            continue;
        if (board[row][col]) { //적이라면 공격 표시하고 break
            board[row][col] = 2;
            break;
        }
        for (int i = 0; i < 3; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;

            if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && (dist[nr][nc] == D)) { //범위 내에 있는 미방문 지점
                dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                q.push(make_pair(nr, nc));
            }
        }
    }
}

void target(int idx, int line) {
    for (int i = 0; i < 3; i++) //3명의 궁수가 공격하게 될 적의 수
        bfs(line, archer[idx][i]);
}

int shoot(int line) {
    int cnt = 0; //공격한 적의 수
    for (int i = 0; i < line; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 2) {
                board[i][j] = 0;
                cnt++;
            }
        }
    }
    return cnt;
}

void move(int line) { //적 이동(궁수 이동으로 구현)
    for (int i = 0; i < M; i++) {
        if (board[line][i]) //궁수 바로 앞에 있던 적들 삭제(성으로 들어옴)
            board[line][i] = 0;
    }
}

int main() {
    int result = 0;

    cin >> N >> M >> D;
    board.assign(N + 1, vector<int>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> board[i][j];
    }
    archerPos(); //가능한 궁수 배치
    vector<vector<int>> tmp = board;
    for (int i = 0; i < archer.size(); i++) {
        board = tmp; //복사
        int line = N, attack = 0;
        while (line) { //적들이 성에 전부 들어오지 않았다면
            target(i, line); //공격하게 될 적
            attack += shoot(line); //공격
            move(line - 1); //적 이동
            line--;
        }
        result = max(result, attack); //최댓값 갱신
    }
    cout << result;
}

전체 소스코드다.

 

    cin >> N >> M >> D;
    board.assign(N + 1, vector<int>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> board[i][j];
    }

입력을 받고

 

    archerPos(); //가능한 궁수 배치

가능한 모든 궁수 배치를 찾는다.

 

void archerPos() {
    for (int i = 0; i < (1 << M); i++) { //비트마스크
        vector<int> tmp;
        for (int j = 0; j < M; j++) {
            if (i & (1 << j))
                tmp.push_back(j);
        }
        if (tmp.size() == 3) //배치된 궁수가 3명이라면
            archer.push_back(tmp);
    }
}

비트마스크로 조합을 구현했다.

 

    vector<vector<int>> tmp = board;

tmp에 board를 저장해두고

 

    vector<vector<int>> tmp = board;
    for (int i = 0; i < archer.size(); i++) {
        board = tmp; //복사
        int line = N, attack = 0;
        while (line) { //적들이 성에 전부 들어오지 않았다면
            target(i, line); //공격하게 될 적
            attack += shoot(); //공격
            move(line - 1); //적 이동
            line--;
        }
        result = max(result, attack); //최댓값 갱신
    }

모든 궁수 배치에 대해서 시뮬레이션을 돌려본다.

 

        int line = N, attack = 0;
        while (line) { //적들이 성에 전부 들어오지 않았다면
            target(i, line); //공격하게 될 적
            attack += shoot(); //공격
            move(line - 1); //적 이동
            line--;
        }

line은 궁수들이 위치한 행이다.

처음엔 N+1에 위치한다고 했으므로 인덱스는 N이다.

 

아까 풀이에서 말한대로

target으로 궁수가 공격할 적을 표시하고,

shoot으로 공격한 뒤, 그 수를 attack에 더해주고,

move로 궁수를 이동해서 적이 이동한 것과 같은 기능을 한다.

 

void target(int idx, int line) {
    for (int i = 0; i < 3; i++) //3명의 궁수가 공격하게 될 적의 수
        bfs(line, archer[idx][i]);
}

3명의 궁수에 대해 bfs를 돌며 공격할 적을 표시한다.

 

void bfs(int r, int c) {
    vector<vector<int>> dist(N + 1, vector<int>(M, D));
    queue<pp> q;
    dist[r][c] = 0;
    q.push(make_pair(r, c));

    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        if (dist[row][col] > D) //더이상 탐색할 필요 없음
            continue;
        if (board[row][col]) { //적이라면 공격 표시하고 break
            board[row][col] = 2;
            break;
        }
        for (int i = 0; i < 3; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;

            if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && (dist[nr][nc] == D)) { //범위 내에 있는 미방문 지점
                dist[nr][nc] = dist[row][col] + 1; //거리 갱신
                q.push(make_pair(nr, nc));
            }
        }
    }
}

그냥 평범한 bfs 함수다.

다만 D보다 먼 거리의 정점은 탐색하지 않도록 하고, 적을 찾았다면 board[row][col] = 2로 표시한 뒤, break한다.

 

int shoot(int line) {
    int cnt = 0; //공격한 적의 수
    for (int i = 0; i < line; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 2) {
                board[i][j] = 0;
                cnt++;
            }
        }
    }
    return cnt;
}

board를 돌면서 2로 표시된 적들을 모두 0으로 바꿔주며 cnt를 늘려준다.

 

void move(int line) { //적 이동(궁수 이동으로 구현)
    for (int i = 0; i < M; i++) {
        if (board[line][i]) //궁수 바로 앞에 있던 적들 삭제(성으로 들어옴)
            board[line][i] = 0;
    }
}

그리고 궁수를 이동한다.

 

        result = max(result, attack); //최댓값 갱신

이런식으로 한 조합에 대한 시뮬레이션이 끝나면 최댓값을 갱신하면 된다.