궤도
[백준] 17135번 : 캐슬 디펜스 본문
문제
풀이
각 턴마다 해야하는 일을 순서대로 써보자.
1. 궁수가 적을 타겟팅
2. 동시에 공격
3. 적 이동
둘 이상의 궁수가 하나의 적을 공격할 수 있다고 하니 타겟팅만 해두고 한번에 공격해야 한다.
궁수의 공격 범위는 반지름이 d인 반원의 형태라고 볼 수 있는데, 그래서 좌, 상, 우의 순서로 탐색하다 제일 먼저 찾은 적을 공격하면 된다.
https://myunji.tistory.com/378
가능한 모든 후보를 찾고 정렬했던 이 문제보단 편한 셈이다.
동시에 공격하면서 공격한 적의 수를 세면 될 것이고...
적을 이동할 때 판을 그대로 복사해서 아래로 미는 건 좀 비효율적일 것 같다.
그래서 궁수를 이동하기로 했다. 궁수들을 맨 아랫줄부터 한 줄씩 위로 올리면 적이 이동하는 것과 같은 기능을 한다.
궁수가 있는 행을 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); //최댓값 갱신
이런식으로 한 조합에 대한 시뮬레이션이 끝나면 최댓값을 갱신하면 된다.