문제 출처
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
테스트 케이스
6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0
answer:14
알고리즘 분류
Brute Force
BFS
풀이
시간제한은 1초입니다. O(n)인 경우 n = (1억)일 때 약 1초가 걸립니다. N과 M이 모두 15보다 작거나 같으므로 (15^7 = 11390625 < 작성한 코드의 시간복잡도 < 15 ^ 7 = 170859375)입니다. N과 M의 범위가 매우 작아서 6중 for문까지 쓸 수 있으므로 브루트포스일 확률이 매우 높습니다. 우선 main 부분입니다.
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> D;
vector<vector<int>> grid(N + 1, vector<int>(M + 1));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> grid[i][j];
for (int i = 1; i <= M; i++)
for (int j = i + 1; j <= M; j++)
for (int k = j + 1; k <= M; k++)
BFS(N, M, grid, i, j, k);
cout << result;
return 0;
}행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D를 입력받습니다. 변수 이름이 grid(격자판)인 2차원 벡터를 선언하고 숫자(1과 0)을 입력받습니다. 궁수 3명을 배치시키는 경우는 M개 중 3개를 순서 상관없이 뽑는 조합입니다(MC3).
궁수를 배치한 뒤에 BFS 이름의 함수를 실행합니다.
int dx[3] = { -1, 0, 1 };
int dy[3] = { 0, -1, 0 };
queue <pair<int, int>> q;
void BFS(int N, int M, vector<vector<int>> grid, int x, int y, int z)
{
vector<vector<int>> cgrid(N + 1, vector<int>(M + 1));
copy(grid.begin(), grid.end(), cgrid.begin());
int archer[3] = { x, y, z };
int pos = N + 1, kill = 0;
vector<vector<bool>> check(N + 1, vector<bool>(M + 1));
while (pos > 1)
{
for (int i = 0; i < 3; i++)
{
vector<vector<bool>> visit(N + 1, vector<bool>(M + 1));
q = queue<pair<int, int>>();
q.push({ archer[i], pos - 1 });
while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;
q.pop();
visit[cy][cx] = true;
if (cgrid[cy][cx] == 1)
{
check[cy][cx] = true;
break;
}
for (int j = 0; j < 3; j++)
{
int nx = cx + dx[j];
int ny = cy + dy[j];
if (nx >= 1 && nx <= M && ny >= 1 && ny <= N)
{
if ((abs(archer[i] - nx) + abs(pos - ny) <= D) && (!visit[ny][nx]))
q.push({ nx, ny });
}
}
}
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
if (check[i][j])
cgrid[i][j] = 0;
pos--;
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
if (check[i][j])
kill++;
result = max(result, kill);
}
궁수가 공격할 수 있는 거리는 궁수 위치에서부터 좌, 상, 우 방향으로 BFS를 실행했을 때의 깊이입니다. 공격할 수 있는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고 거리가 D 이하인 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 합니다. 그러므로 깊이 1부터 탐색해야 하고 방향은 왼쪽, 위쪽, 오른쪽 순으로 탐색해야 합니다.
BFS 함수를 여러 번 실행해야 하므로 원본인 grid가 바뀌어서는 안 되기 때문에 입력받은 grid를 cgrid에 복사합니다. 궁수 행 위치인 pos와 죽인 적의 수인 kill을 선언해 줍니다. 궁수 2명이 같은 적을 공격할 수도 있으므로 check(2차원 벡터)에 체크해 놓기 위해 선언해 줍니다. pos = 1일 때까지(1번째 행까지) 첫 번째 궁수, 두 번째 궁수, 세번 째 궁수 각각 좌, 상, 우 순서로 탐색해 줍니다.
Queue에 행과 열을 넣어줍니다. 방문 여부인 visit을 true로 바꿔주고 만약 격자판 값인 cgrid = 1이면 적을 공격해야 하므로 check를 true로 바꿔줍니다. 공격이 끝났으므로 break;해줍니다. 좌, 상, 우로 탐색하는 부분입니다. 범위 외의 값은 제외 해주고 |r1-r2| + |c1-c2|를 계산해 D보다 작거나 같고 방문하지 않았다면 Queue에 넣어줍니다. 중복하는 적을 공격하는 경우가 있으므로 공격한 부분 값을 0으로 바꾸어 줍니다. while문 마지막 줄에 pos--를 해주고 loop를 다시 돌려 줍니다.
while문이 모두 끝난 뒤에(BFS 탐색이 끝난 뒤에) checked에 표시된 수만큼 kill에 더해 줍니다. result와 kill 중 큰 값을 result에 저장해주고 함수를 종료해 줍니다.
시간복잡도 계산
O(MC3 x (1[vector copy] x N[while pos] x (3[궁수 3명] x (N x M[정점] + 3[간선 최대 3개][BFS]) + N x M) + N x M))
n = 15 m = 15일 때 최대일 떄 6,306,300(칠백만 이하)이므로 1억을 넘지 않아 시간초과에 걸리지 않습니다.
전체 코드
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int N, M, D;
int result = 0;
int dx[3] = { -1, 0, 1 };
int dy[3] = { 0, -1, 0 };
queue <pair<int, int>> q;
void BFS(int N, int M, vector<vector<int>> grid, int x, int y, int z)
{
vector<vector<int>> cgrid(N + 1, vector<int>(M + 1));
copy(grid.begin(), grid.end(), cgrid.begin());
int archer[3] = { x, y, z };
int pos = N + 1, kill = 0;
vector<vector<bool>> check(N + 1, vector<bool>(M + 1));
while (pos > 1)
{
for (int i = 0; i < 3; i++)
{
vector<vector<bool>> visit(N + 1, vector<bool>(M + 1));
q = queue<pair<int, int>>();
q.push({ archer[i], pos - 1 });
while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;
q.pop();
visit[cy][cx] = true;
if (cgrid[cy][cx] == 1)
{
check[cy][cx] = true;
break;
}
for (int j = 0; j < 3; j++)
{
int nx = cx + dx[j];
int ny = cy + dy[j];
if (nx >= 1 && nx <= M && ny >= 1 && ny <= N)
{
if ((abs(archer[i] - nx) + abs(pos - ny) <= D) && (!visit[ny][nx]))
q.push({ nx, ny });
}
}
}
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
if (check[i][j])
cgrid[i][j] = 0;
pos--;
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
if (check[i][j])
kill++;
result = max(result, kill);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> D;
vector<vector<int>> grid(N + 1, vector<int>(M + 1));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> grid[i][j];
for (int i = 1; i <= M; i++)
for (int j = i + 1; j <= M; j++)
for (int k = j + 1; k <= M; k++)
BFS(N, M, grid, i, j, k);
cout << result;
return 0;
}