포탑 부수기
Simulation, BFS
- 평균 : 180;
sol : 232' 54''
- 수행 시간 : 10ms
- 메모리 : 0MB
Learnings
- 대각 좌표 보정을 틀려서 1시간 넘게 헤맴.
- 방향 우선 BFS 잘 구현해놓고 여기서 1시간 가까이 디버깅함.
-> 기본기가 약해졌다. 핑계 금지.- 앞으로는 코드 작성시 애매한 부분이 있으면 Debug 체크를 해두자.
pair<int, int> GoThrough(int i, int j) { if (i < 1) i = n; if (i > n) i = 1; if (j < 1) j = m; if (j > m) j = 1; return make_pair(i, j); }
- Tuple 비교 방식을 적극 활용하자.
Turret* select_target(Turret* attacker) { tuple<int,int,int,int> strongest_criteria = {INT_MIN, INT_MIN, INT_MIN, INT_MIN}; Turret* target = nullptr; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { Turret& turret = turrets[i][j]; if (turret.is_broken || &turret == attacker) continue; tuple<int,int,int,int> current_criteria = { turret.atk, -turret.last_atk, -(turret.x + turret.y), -turret.y }; if (current_criteria > strongest_criteria) { strongest_criteria = current_criteria; target = &turret; } } } return target; }
My code
#include <iostream>
#include <utility>
#include <queue>
#include <tuple>
#define MAX_N 11
#define MAX_M 11
#define DESTROYED 0
using namespace std;
int n, m, k;
int turn;
bool isInterrupted;
// 포탑들의 현상태를 기록하는 그리드
int turretGrid[MAX_N][MAX_M];
// 공격한 라운드 번호를 기록하는 그리드
int historyGrid[MAX_N][MAX_M];
// 공격과의 관련 여부를 기록하는 그리드
bool isAttackRelated[MAX_N][MAX_M];
pair<int, int> attacker;
pair<int, int> target;
pair<int, int> fromWhere[MAX_N][MAX_M];
// 우, 하, 좌, 상 | 대각성분
int ds[8][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0 }, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
////////////////////////////// FUNDAMENTAL FUNCTIONS //////////////////////////////
void Debug() {
cout << endl << "DEBUG" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << turretGrid[i][j] << ' ';
}
cout << endl;
}
cout << "DEBUG FIN" << endl;
}
void DebugFW() {
cout << endl << "DEBUG" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << "(" << fromWhere[i][j].first << "," << fromWhere[i][j].second << ")" << ' ';
}
cout << endl;
}
cout << "DEBUG FIN" << endl;
}
void Init() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> turretGrid[i][j];
}
}
}
void InitFromWhere() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
fromWhere[i][j] = make_pair(-1, -1);
}
}
}
void InitIsAttackRelated() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
isAttackRelated[i][j] = false;
}
}
}
////////////////////////////// FUNDAMENTAL FUNCTIONS //////////////////////////////
void SelectAttacker() {
attacker = make_pair(-1, -1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (turretGrid[i][j] == DESTROYED) continue;
// 처음 발견한 경우
if (attacker.first == -1 && attacker.second == -1) {
attacker = make_pair(i, j);
}
// 더 작은 공격력을 가진 포탑을 발견한 경우
else if (turretGrid[i][j] < turretGrid[attacker.first][attacker.second]) {
attacker = make_pair(i, j);
}
// 만약 공격력이 같을 경우
else if (turretGrid[i][j] == turretGrid[attacker.first][attacker.second]) {
// 가장 최근에 공격한 포탑
if (historyGrid[i][j] > historyGrid[attacker.first][attacker.second]) {
attacker = make_pair(i, j);
}
// 히스토리도 같다면
else if (historyGrid[i][j] == historyGrid[attacker.first][attacker.second]) {
// 행과 열의 합이 가장 큰 포탑
if (i + j > attacker.first + attacker.second) {
attacker = make_pair(i, j);
}
// 행과 열의 합이 같다면
else if (i + j == attacker.first + attacker.second) {
// 열 값이 가장 큰 포탑
if (j > attacker.second) {
attacker = make_pair(i, j);
}
}
}
}
}
}
isAttackRelated[attacker.first][attacker.second] = true;
// DEBUG
//cout << "chosen attacker : " << attacker.first << " " << attacker.second << endl;
}
void EnforceAttacker() {
if (attacker.first == -1 && attacker.second == -1) {
cout << "There's no turret available";
return;
}
turretGrid[attacker.first][attacker.second] += (n + m);
}
void SelectTarget() {
target = make_pair(-1, -1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 이미 부서진 포탑이거나 공격자 좌표인 경우 패스
if (turretGrid[i][j] == DESTROYED || (attacker.first == i && attacker.second == j)) continue;
// 처음 발견한 경우
if (target.first == -1 && target.second == -1) {
target = make_pair(i, j);
}
// 더 큰 공격력을 가진 포탑을 발견한 경우
else if (turretGrid[i][j] > turretGrid[target.first][target.second]) {
target = make_pair(i, j);
}
// 만약 공격력이 같을 경우
else if (turretGrid[i][j] == turretGrid[target.first][target.second]) {
// 가장 오래전에 공격한 포탑
if (historyGrid[i][j] < historyGrid[target.first][target.second]) {
target = make_pair(i, j);
}
// 히스토리도 같다면
else if (historyGrid[i][j] == historyGrid[target.first][target.second]) {
// 행과 열의 합이 가장 작은 포탑
if (i + j < target.first + target.second) {
target = make_pair(i, j);
}
// 행과 열의 합이 같다면
else if (i + j == target.first + target.second) {
// 열 값이 가장 작은 포탑
if (j < target.second) {
target = make_pair(i, j);
}
}
}
}
}
}
isAttackRelated[target.first][target.second] = true;
// DEBUG
//cout << "chosen target : " << target.first << " " << target.second << endl;
}
bool InGrid(int i, int j) {
return 1 <= i && i <= n && 1 <= j && j <= m;
}
pair<int, int> GoThrough(int i, int j) {
if (i == 0) i = n;
else if (i == n + 1) i = 1;
if (j == 0) j = m;
else if (j == m + 1) j = 1;
return make_pair(i, j);
}
bool CanGo(int i, int j) {
if (fromWhere[i][j].first == -1 && fromWhere[i][j].second == -1 && turretGrid[i][j] != DESTROYED) return true;
else return false;
}
void CheckDestroyed() {
int turretCnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (turretGrid[i][j] <= 0) {
turretGrid[i][j] = DESTROYED;
}
else turretCnt++;
}
}
if (turretCnt == 1) {
isInterrupted = true;
}
}
bool LaserAttack() {
InitFromWhere();
queue<pair<int, int>> q;
bool succeeded = false;
int damage = turretGrid[attacker.first][attacker.second];
fromWhere[attacker.first][attacker.second] = attacker;
q.push(attacker);
while (!q.empty()) {
if (succeeded) break;
int ci = q.front().first, cj = q.front().second;
q.pop();
// DEBUG
//cout << "cur indices : " << ci << ", " << cj << endl;
for (int d = 0; d < 4; d++) {
int ni = ci + ds[d][0], nj = cj + ds[d][1];
if (!InGrid(ni, nj)) {
// 가장자리에서 막힌 방향으로 진행하고자 한다면, 반대편으로 나온다.
tie(ni, nj) = GoThrough(ni, nj);
}
// 이동 가능 조건 : 아직 방문하지 않았고, 포탑이 부서진 자리가 아닌 경우
if (CanGo(ni, nj)) {
// 타겟에 도착했을 경우
if (ni == target.first && nj == target.second) {
fromWhere[ni][nj] = make_pair(ci, cj);
succeeded = true;
turretGrid[ni][nj] -= damage;
// DEBUG
//cout << "succeeded!" << endl;
break;
}
else {
fromWhere[ni][nj] = make_pair(ci, cj);
q.push(make_pair(ni, nj));
}
}
}
}
// 레이저 공격에 성공했을 경우 레이저 경로상 포탑들에게도 데미지를 준다.
if (succeeded) {
// 데미지는 기존 공격력의 절반.
damage /= 2;
// DEBUG
//cout << "Laser attacked" << endl;
int ci, cj, ni, nj;
tie(ci, cj) = target;
tie(ni, nj) = fromWhere[target.first][target.second];
bool attackFin = false;
while (!attackFin) {
//DEBUG
//cout << "laser path : " << ci << ", " << cj << endl;
for (int d = 3; d >= 0; d--) {
// 우, 하, 좌, 상 순으로 우선 순위이므로 역으로 접근하여 우선 순위 확보.
ni = ci + ds[d][0], nj = cj + ds[d][1];
if (!InGrid(ni, nj)) {
tie(ni, nj) = GoThrough(ni, nj);
}
if (fromWhere[ni][nj].first != -1 && fromWhere[ni][nj].second != -1) {
tie(ci, cj) = fromWhere[ci][cj];
if (ci == attacker.first && cj == attacker.second) {
attackFin = true;
break;
}
else {
// 경로상 포탑에 피해를 입힌다.
turretGrid[ci][cj] -= damage;
// 공격 관련 여부에 표시한다.
isAttackRelated[ci][cj] = true;
break;
}
}
}
}
}
return succeeded;
}
void ShellAttack() {
int damage = turretGrid[attacker.first][attacker.second];
// 1. 공격 대상에 포탄을 던져 공격력 만큼 피해를 입힌다.
turretGrid[target.first][target.second] -= damage;
// 2. 주위 8개 방향에 있는 포탑은 절반의 피해를 입는다.
damage /= 2;
int ci = target.first, cj = target.second;
for (int d = 0; d < 8; d++) {
int ni = ci + ds[d][0], nj = cj + ds[d][1];
// 만약 가장자리에 포탄이 떨어졌다면, 추가 피해가 반대편 격자에 미치게 된다.
if (!InGrid(ni, nj)) {
tie(ni, nj) = GoThrough(ni, nj);
}
// 단, 공격자는 영향을 받지 않는다.
if (ni == attacker.first && nj == attacker.second) continue;
// 포탑이 존재하면
if (turretGrid[ni][nj] != DESTROYED) {
turretGrid[ni][nj] -= damage;
isAttackRelated[ni][nj] = true;
}
}
// DEBUG
//cout << "Shell attacked" << endl;
}
void Attack() {
// 1. Laser attack
bool laserSucceeded = LaserAttack();
// 2. If Laser unavailable, shell attack
if (!laserSucceeded) {
ShellAttack();
}
// 3. attack history update
historyGrid[attacker.first][attacker.second] = turn;
}
void Reinforce() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (turretGrid[i][j] != DESTROYED && !isAttackRelated[i][j]) {
turretGrid[i][j] += 1;
}
}
}
}
void PrintStrongestPower() {
int maxPower = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (turretGrid[i][j] != DESTROYED) {
maxPower = (maxPower < turretGrid[i][j]) ? turretGrid[i][j] : maxPower;
}
}
}
cout << maxPower;
}
int main() {
Init();
while (++turn <= k) {
// 하나의 턴은 다음의 4가지 액션을 순서대로 수행하며, 총 K번 반복됩니다.
// 만약 부서지지 않은 포탑이 1개가 된다면 그 즉시 중지됩니다.
// 0. 공격 관련 여부 초기화
InitIsAttackRelated();
// 1. 공격자 선정 & 공격력 증가
SelectAttacker();
EnforceAttacker();
// 2. 공격자의 공격
SelectTarget();
Attack();
// DEBUG
//cout << "after attack";
//Debug();
// 3. 포탑 부서짐
CheckDestroyed();
if (isInterrupted) break;
// 4. 포탑 정비
Reinforce();
// DEBUG
//cout << "after reinforce";
//Debug();
}
PrintStrongestPower();
}