[코드트리] 포탑 부수기

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/submissions?page=1&pageSize=20

💻 문제 풀이 : C++

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

using namespace std;

struct Coord {
	int r, c;
};

struct Attack {
	int r, c;
};

struct Defense {
	int r, c;
};

int N, M, K;
// 포탑 공격력
int HP[12][12];
// 포탑 최근 공격시간
int TIME[12][12];
// 공격 관련됐는지
int REPAIR[12][12];

// 공격자 선정용 우선순위 큐
priority_queue<Attack> attacker;
// 수비자 선정용 우선순위 큐
priority_queue<Defense> defenser;

// 우, 하, 좌, 상 + 대각선
int dr[] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int dc[] = { 1, 0, -1, 0, 1, -1, 1, -1 };

int visited[12][12];
int dirt[12][12];

int answer;

// 공격자 선정 우선순위 정하기
bool operator<(Attack a, Attack b)
{
	// 공격력이 낮은 포탑
	if (HP[a.r][a.c] > HP[b.r][b.c]) return true;
	if (HP[a.r][a.c] < HP[b.r][b.c]) return false;
	// 가장 최근에 공격한 포탑
	if (TIME[a.r][a.c] < TIME[b.r][b.c]) return true;
	if (TIME[a.r][a.c] > TIME[b.r][b.c]) return false;
	// 행과 열의 합이 가장 큰 포탑
	if (a.r + a.c < b.r + b.c) return true;
	if (a.r + a.c > b.r + b.c) return false;
	// 열이 가장 큰 포탑
	if (a.c < b.c) return true;
	if (a.c > b.c) return false;
	return false;
}

// 수비 선정 우선순위 정하기
bool operator<(Defense a, Defense b)
{
	// 공격력이 높은 포탑
	if (HP[a.r][a.c] < HP[b.r][b.c]) return true;
	if (HP[a.r][a.c] > HP[b.r][b.c]) return false;
	// 가장 공격한 지 오래된 포탑
	if (TIME[a.r][a.c] > TIME[b.r][b.c]) return true;
	if (TIME[a.r][a.c] < TIME[b.r][b.c]) return false;
	// 행과 열의 합이 가장 작은 포탑
	if (a.r + a.c > b.r + b.c) return true;
	if (a.r + a.c < b.r + b.c) return false;
	// 열이 가장 작은 포탑
	if (a.c > b.c) return true;
	if (a.c < b.c) return false;
	return false;
}

int turnBack(int d)
{
	if (d == 0) return 2;
	else if (d == 1) return 3;
	else if (d == 2) return 0;
	else if (d == 3) return 1;
}

int isOneFort()
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (HP[i][j] != 0) cnt++;
		}
	}
	if (cnt == 1) return 1;
	else return 0;
}

int getStrongestTurret()
{
	int tmpMax = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			tmpMax = max(tmpMax, HP[i][j]);
		}
	}
	return tmpMax;
}

void getRepair()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (HP[i][j] == 0) continue;
			if (!REPAIR[i][j]) HP[i][j] += 1;
		}
	}
}

int attackFort(int s_r, int s_c, int e_r, int e_c)
{
	// 공격대상 피해
	HP[e_r][e_c] -= HP[s_r][s_c];
	if (HP[e_r][e_c] < 0) HP[e_r][e_c] = 0;
	// 주변 8방향 피해
	for (int i = 0; i < 8; i++)
	{
		int nr = (e_r + dr[i] + N) % N;
		int nc = (e_c + dc[i] + M) % M;
		// 공격자는 면역
		if (nr == s_r && nc == s_c) continue;
		if (HP[nr][nc] == 0) continue;
		HP[nr][nc] -= HP[s_r][s_c] / 2;
		if (HP[nr][nc] < 0) HP[nr][nc] = 0;
		REPAIR[nr][nc] = 1;
	}

	return 0;
}

int attackLaser(int s_r, int s_c, int e_r, int e_c)
{
	memset(visited, 0, sizeof(visited));

	queue<Coord> nowQ;
	nowQ.push({s_r, s_c});
	visited[s_r][s_c] = 1;
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			Coord next = { (now.r + dr[i] + N) % N,
				(now.c + dc[i] + M) % M };
			// 부서진 포탑 X
			if (HP[next.r][next.c] == 0) continue;
			// 공격대상에 도착하는 경우
			if (next.r == e_r && next.c == e_c)
			{
				dirt[next.r][next.c] = turnBack(i);
				// 방문기록을 초기화하고
				memset(visited, 0, sizeof(visited));
				// 공격대상부터 공격자까지 경로 추적	
				int tmp_r = e_r;
				int tmp_c = e_c;
				while (!(tmp_r == s_r && tmp_c == s_c))
				{
					int new_r = (tmp_r + dr[dirt[tmp_r][tmp_c]] + N) % N;
					int new_c = (tmp_c + dc[dirt[tmp_r][tmp_c]] + M) % M;
					visited[new_r][new_c] = 1;
					tmp_r = new_r;
					tmp_c = new_c;
				}
				// 공격대상 피해
				HP[e_r][e_c] -= HP[s_r][s_c];
				if (HP[e_r][e_c] < 0) HP[e_r][e_c] = 0;
				// 레이저 경로 피해
				for (int i = 0; i < N; i++)
				{
					for (int j = 0; j < M; j++)
					{
						// 공격자는 영향 X
						if (i == s_r && j == s_c) continue;
						// 공격력의 절반만큼 피해
						if (visited[i][j])
						{
							HP[i][j] -= HP[s_r][s_c] / 2;
							if (HP[i][j] < 0) HP[i][j] = 0;
							REPAIR[i][j] = 1;
						}
					}
				}
				return 1;
			}
			if (visited[next.r][next.c] != 0) continue;
			visited[next.r][next.c] += visited[now.r][now.c] + 1;
			dirt[next.r][next.c] = turnBack(i);
			nowQ.push(next);
		}
	}
	return 0;
}

void findWeakTurret(int &r, int &c)
{
	// attacker 우선순위 큐 초기화
	while (!attacker.empty()) attacker.pop();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (HP[i][j] == 0) continue;
			attacker.push({ i, j });
		}
	}
	r = attacker.top().r;
	c = attacker.top().c;
}

void findStrongTurret(int &r, int &c)
{
	// defenser 우선순위 큐 초기화
	while (!defenser.empty()) defenser.pop();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (HP[i][j] == 0) continue;
			defenser.push({ i, j });
		}
	}
	r = defenser.top().r;
	c = defenser.top().c;
}

void CLEAR()
{

}

void INPUT()
{
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> HP[i][j];
		}
	}
}

void SOLVE()
{
	int turn = 1;
	while (turn <= K)
	{
		memset(REPAIR, 0, sizeof(REPAIR));
		int attack_r, attack_c, defense_r, defense_c;
		// 공격자 찾기 - 약한 포탑
		findWeakTurret(attack_r, attack_c);
		REPAIR[attack_r][attack_c] = 1;
		// 공격대상 찾기 - 강한 포탑
		findStrongTurret(defense_r, defense_c);
		REPAIR[defense_r][defense_c] = 1;
		// 공격력 증가
		HP[attack_r][attack_c] += N + M;
		// 레이저 공격 시도
		int isLaserOkay = attackLaser(attack_r, attack_c, defense_r, defense_c);
		// 레이저 공격 실패했으면 포탄 공격
		if (!isLaserOkay)
		{
			isLaserOkay = attackFort(attack_r, attack_c, defense_r, defense_c);
		}
		// 공격시간 반영
		TIME[attack_r][attack_c] = turn;
		// 포탑 정비
		getRepair();
		// 포탑 1개면 중지
		if (isOneFort()) break;
		turn++;
	}
	// 가장 포탑의 공격력 출력
	answer = getStrongestTurret();

	cout << answer << endl;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

---

📌 memo 😊
✔️ BFS로 거리탐색할 때 시작점도 방문표시 해주기!

• 시작점부터 거리가 +1씩 증가하므로, 꼭 넣어주어야 함

✔️ 포탑이 1개일 때 종료되는 조건을 놓쳤다. 문제 꼼꼼히 읽기!