[코드트리] 포탑 부수기 (C++)

[문제] 

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[설명] 

보기에는 다른 빡구현 문제들보다 할만할 줄 알았는데 결국 이것도 문제가 있었다. 공격자로 부터 타겟 까지 가는 최단 경로를 구하는 것이 문제였는데, 처음엔 단지 BFS로 최단 경로를 찾고, 공격자에서 타겟으로 가는 우선순위를 반대로 뒤집어서 따라가도록 하였다. 근데 이렇게 하면 안되는 거였다. 

 

여기서 부터는 해설을 좀 보았는데, BFS에서 nx, ny 좌표에 이전 좌표를 맵핑하는 방법이있었다. 이방법을 보고 또 배열에 x,y 좌표를 맵핑하려면 3차원이 필요한가? 생각도 들었는데 단순히 배열을 두개 만들어서 x,y 좌표를 따로 보관하면 되었다. 

 

한가지 알고리즘을 구현하는데에 너무 많은 시간을 들이면 꼬이기 시작하는거 같다.....

 

 

[코드] 

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

using namespace std;
#define X first
#define Y second


int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int dx1[4] = { 0,-1,0,-1};
int dy1[4] = { -1,0,1,0 };
int dx2[8] = { -1,0,1,0,1,1,-1,-1 };
int dy2[8] = { 0,-1,0,1,1,-1,1,-1 };

int N, M, K, T;
int board[11][11];
int dis[11][11];
int disx[11][11];
int disy[11][11];

bool BFS_flag;
struct tower {
	int num;
	int x, y;
	int time; //최근 공격한 시간
	int power;
	bool out;
};

vector <tower> towers;
vector <tower> attackers;
vector <tower> targets;
tower attacker;
tower target;


bool cmp1(tower& a, tower& b) {
	if (a.power < b.power) return true;
	else if (a.power == b.power) {
		if (a.time > b.time) return true;
		else if (a.time == b.time) {
			if (a.x + a.y > b.x + b.y) return true;
			else if (a.x + a.y == b.x + b.y) {
				if (a.y > b.y) return true;
			}
		}
	}
	return false;
}

bool cmp2(tower& a, tower& b) {
	if (a.power > b.power) return true;
	else if (a.power == b.power) {
		if (a.time < b.time) return true;
		else if (a.time == b.time) {
			if (a.x + a.y < b.x + b.y) return true;
			else if (a.x + a.y == b.x + b.y) {
				if (a.y < b.y) return true;
				return false;
			}
		}
	}
	return false;
}

void find_attacker() {
	attackers.clear();

	int min_val = 10000;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] >= 1)
				min_val = min(board[i][j], min_val);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (min_val == board[i][j])
			{
				for (int k = 0; k < towers.size(); k++)
					if (towers[k].x == i && towers[k].y == j && !towers[k].out)
						attackers.push_back(towers[k]); //후보 넣음.
			}
		}
	}
	sort(attackers.begin(), attackers.end(), cmp1);
	attacker = attackers[0];
	attacker.power += M + N;
	attacker.time = T;
	towers[attacker.num] = attacker;
	board[attacker.x][attacker.y] = attacker.power;
}

void find_target() {
	targets.clear();
	int max_val = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (attacker.x == i && attacker.y == j) continue;
			if (board[i][j] >= 1)
				max_val = max(board[i][j], max_val);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (attacker.x == i && attacker.y == j) continue;
			if (max_val == board[i][j])
			{
				for (int k = 0; k < towers.size(); k++)
					if (towers[k].x == i && towers[k].y == j && !towers[k].out)
						targets.push_back(towers[k]); //후보 넣음.
			}
		}
	}
	sort(targets.begin(), targets.end(), cmp2);
	target = targets[0];
}

void BFS() {
	queue <pair<int, int>> q;
	bool vis[11][11] = { false, };
	vis[attacker.x][attacker.y] = 1;
	dis[attacker.x][attacker.y] = 1;
	q.push({ attacker.x, attacker.y });
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];
			if (nx == N) nx = 0;
			if (ny == M) ny = 0;
			if (nx == -1) nx = N - 1;
			if (ny == -1) ny = M - 1;
			if (vis[nx][ny]) continue;
			if (board[nx][ny] == 0) continue;

			q.push({ nx,ny });
			vis[nx][ny] = true;
			dis[nx][ny] = dis[cur.X][cur.Y] + 1;
			disx[nx][ny] = cur.X;
			disy[nx][ny] = cur.Y;
		}
	}
	if (dis[target.x][target.y] == 0) BFS_flag = false;
}

void back_BFS() {
	bool flag = false;
	pair <int, int> cur = { target.x, target.y };
	board[target.x][target.y] -= attacker.power;
	while (true) {
		if (cur.X == attacker.x && cur.Y == attacker.y) break;
		if (flag)
			board[cur.X][cur.Y] -= attacker.power / 2;
		int nx = disx[cur.X][cur.Y];
		int ny = disy[cur.X][cur.Y];
		cur = { nx, ny };
		flag = true;
	}
}
void fire() {
	pair <int, int> cur = { target.x, target.y };
	board[target.x][target.y] -= attacker.power;
	for (int i = 0; i < 8; i++) {
		int nx = cur.X + dx2[i];
		int ny = cur.Y + dy2[i]; //반대방향 우선순위
		if (nx == N) nx = 0;
		if (ny == M) ny = 0;
		if (nx == -1) nx = N - 1;
		if (ny == -1) ny = M - 1;

		if (nx == attacker.x && ny == attacker.y) continue;
		if (board[nx][ny] != 0)
		{
			board[nx][ny] -= attacker.power / 2;;
		}
	}
}

int main() {
	cin >> N >> M >> K;
	int index = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if (board[i][j] > 0)
			{
				towers.push_back({ index, i,j,0,board[i][j],false });
				index++;
			}
		}
	}
	T = 1;
	while (true) {
		if (K == 0) break;
		BFS_flag = true;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				dis[i][j] = 0;
			}
		}
		find_attacker();
		find_target();
		BFS();
		if (BFS_flag)
			back_BFS();
		else
			fire();

		//파워, 보드 갱신
		for (int i = 0; i < towers.size();i++) {
			if (towers[i].out || i == attacker.num) continue;
			if (board[towers[i].x][towers[i].y] == towers[i].power) //피해안받음
			{
				towers[i].power++;
				board[towers[i].x][towers[i].y]++;
			}
			if (board[towers[i].x][towers[i].y] <= 0) {
				towers[i].power = 0;
				board[towers[i].x][towers[i].y] = 0;
				towers[i].out = true;
			}
			else towers[i].power = board[towers[i].x][towers[i].y];
		}
		int count = 0;
		for (int i = 0; i < towers.size(); i++) {
			if (!towers[i].out)
				count++;

		}

		if (count == 1) break;
		K--;
		T++;
	}

	int ans = 0;
	for (int i = 0; i < towers.size(); i++) {
		if (!towers[i].out)
			ans = max(towers[i].power, ans);

	}
	cout << ans;
}

 

얼마안남았다... 화이팅..!