[ boj : 17135 ] 캐슬 디펜스

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

해설 : 삼성 A형 기출이었는데 천천히 마음 차분하게 한번에 맞는 다는 생각으로 푸시면 할 수 있으실 겁니다.

그게 동작들을 나누어 봐요.

 

어떤 동작이 높은 우선순위를 가져야 하는지, 그리고 그 과정속에서 필요한 조건들을 뽑아내고 이것들이 다음 동작에 어떻게 미치는지

 

먼저 적들이 단 한명이라도 확인을 하고 난 후 화살을 쏴야겠죠. 그 다음 화살에 맞은 적들은 보드판에서 지워줘야 하고, 한줄씩 밑으로 내리면 됩니다.

 

이때 주의할 점은 '동시에' 맞는 적들이 생길 수도 있으니, 화살에 맞은 즉시 지워주는 것이 아니라 정보들을 저장해 준 후 나중에 한번에 처리를 해주는 것이 더 나을수도 있습니다.

 

정렬방법은 연산자 오버라이딩을 통해 간단히 처리를 해줄 수 있겠죠?

궁수는 3명 밖에 안되니 그냥 삼중포문을 돌리면 되고요.

 

#include<bits/stdc++.h>

using namespace std;

class Pair {
public :
	int x, y;
	int tx, ty;
public:
	Pair(int x, int y,int tx,int ty) {
		this->x = x;
		this->y = y;
		this->tx = tx;
		this->ty = ty;
	}
	bool operator<(const Pair& cur) const {
		if (abs(this->x - this->tx) + abs(this->y - this->ty) == abs(cur.x - this->tx) + abs(cur.y - this->ty)) {
			return this->y > cur.y;
		}
		return abs(this->x - this->tx) + abs(this->y - this->ty) > abs(cur.x - this->tx) + abs(cur.y - this->ty);
	}
};

int ans,ret;
int n, m, d;
int board[20][20], cp_board[20][20];
priority_queue<Pair> pq[3];

void shot(int x, int num);
void remove();
void move();
bool check();

int main()
{
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];
	for(int i=0;i<m;i++)
		for(int j=i+1;j<m;j++)
			for (int k = j + 1; k < m; k++) {
				memcpy(cp_board, board, sizeof(board));
				while (!check()) {
					shot(i,0);
					shot(j,1);
					shot(k,2);
					remove();
					move();
				}
				ans = max(ans, ret);
				ret = 0;
			}
	cout << ans;
	return 0;
}
void shot(int x,int num)
{	
	queue<Pair> q;
	int visit[20][20];
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
	memset(visit, 0, sizeof(visit));

	q.push({ n,x,n,x });
	while (!q.empty())
	{
		Pair cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int tx = cur.x + dx[i];
			int ty = cur.y + dy[i];

			if (tx < 0 || tx >= n || ty < 0 || ty >= m)continue;

			if (!visit[tx][ty] && abs(tx-n) + abs(ty-x) <= d) {
				if(cp_board[tx][ty])
					pq[num].push({ tx,ty,n,x });
				q.push({ tx,ty,n,x });
				visit[tx][ty] = 1;
			}
		}
	}
}
void remove()
{
	for (int i = 0; i < 3; i++)
	{
		if (!pq[i].empty()) {
			Pair cur = pq[i].top();
			//이미 다른 궁수가 적을 쐈는지 확인
			if (cp_board[cur.x][cur.y] != 0) {
				cp_board[cur.x][cur.y] = 0;
				ret++;
			}
		}		
	}
	for (int i = 0; i < 3; i++) {
		while (!pq[i].empty())
			pq[i].pop();
	}
}
void move()
{
	queue<int> q[20];
	for (int i = 0; i < m; i++) {
		for (int j = n - 1; j >= 0; j--)
			if (cp_board[j][i]) {
				q[i].push(j);
				cp_board[j][i] = 0;
			}
	}
	for (int i = 0; i < m; i++) {
		while (!q[i].empty()) {
			int t = q[i].front();
			q[i].pop();

			if (t + 1 < n)
				cp_board[t+1][i] = 1;
		}
	}
}
bool check()
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (cp_board[i][j] == 1)
				cnt++;
	return (cnt != 0) ? false : true;
}