[코드트리] 싸움땅 (C++)

[문제]

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

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

 

[설명]

while문을 별로 쓸필요없이 조건마다 분기를 주면 되서 다른 문제보다 조금 쉬웠던것 같다.

문제를 풀며 잘못생각한점이 어차피 총을 버리고 가져갈때, 가장강한 총을 가져가기 때문에 board에 가장 강한 총만 표기하면 된다고 생각했는데, 그게 틀려서 조금 헤멨다. 

board에서 가장 강한총을 가져가버리면 두번째로 강한총이 남아야하므로, 결국 board에 버려진 모든 총을 기록해놔야했다. 그래서 우선순위 큐를 사용해서 가장 위의 총을 가져가고, 현재 총은 pq에 넣어주는 방식을  사용했다.

win 함수를 따로 만들어, 패자와 승자 매개변수만 다르게 해서 여러상황을 쉽게 해결할 수 있었다. 

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

using namespace std;

int N, M, K;
int board[21][21];
int p_board[21][21];
priority_queue <int> pq[21][21];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct person {
	int num;
	int x, y;
	int dir;
	int power;
	int gun;
	int point;
};
vector <person> persons;
void win(person me, person you) {//승자, 패자 행동
	me.point += (me.power + me.gun) - (you.power + you.gun);
	//패자 조건 먼저 
	pq[you.x][you.y].push(you.gun); //패자 총은 그냥 버림
	you.gun = 0;
	while (true)
	{
		int nx = you.x + dx[you.dir];
		int ny = you.y + dy[you.dir];
		if (nx >= N || nx < 0 || ny < 0 || ny >= N || p_board[nx][ny] > 0) {
			you.dir = (you.dir + 1) % 4;
			continue;
		}
		p_board[nx][ny] = you.num;
		you.x = nx;
		you.y = ny;
		break;
	}
	if (!pq[you.x][you.y].empty() && pq[you.x][you.y].top() > you.gun) //움직인 뒤에도..
	{
		int temp = you.gun;
		you.gun = pq[you.x][you.y].top();
		pq[you.x][you.y].pop();
		pq[you.x][you.y].push(temp);
		board[you.x][you.y] = pq[you.x][you.y].top(); //둘총 변경
	}


	persons[you.num] = you;

	if (!pq[me.x][me.y].empty() && pq[me.x][me.y].top() > me.gun) //내총보다 약하면 뭐할필요없음
	{
		int temp = me.gun;
		me.gun = pq[me.x][me.y].top();
		pq[me.x][me.y].pop();
		pq[me.x][me.y].push(temp);
		board[me.x][me.y] =  pq[you.x][you.y].top(); //둘총 변경
	}
	p_board[me.x][me.y] = me.num;
	//승자 조건 끝
	persons[me.num] = me;
};



void move(person me) {
	int nx = me.x + dx[me.dir];
	int ny = me.y + dy[me.dir]; //그냥 이동
	if (nx >= N || nx < 0 || ny < 0 || ny >= N)
	{
		me.dir = (me.dir + 2) % 4; //나가는 경우 방향 전환
		nx = me.x + dx[me.dir];
		ny = me.y + dy[me.dir];
	}
	if (p_board[nx][ny] == 0) //사람없는경우
	{
		p_board[me.x][me.y] = 0;//사람 마다 즉시갱신 필요
		p_board[nx][ny] = me.num;
		if (!pq[nx][ny].empty() && pq[nx][ny].top() > me.gun) //내총보다 약하면 뭐할필요없음
		{
			int temp = me.gun;
			me.gun = pq[nx][ny].top();
			pq[nx][ny].pop();
			pq[nx][ny].push(temp);
			board[nx][ny] = pq[nx][ny].top(); //둘총 변경
		}
		me.x = nx;
		me.y = ny; //위치 이동 후 종료
		persons[me.num] = me;
	}
	else if (p_board[nx][ny] > 0) //사람있는경우
	{
		p_board[me.x][me.y] = 0;
		me.x = nx;
		me.y = ny; //일단 위치 이동: 승자일경우 총을 바꾸기 위해

		person you = persons[p_board[nx][ny]];
		if (me.gun + me.power > you.gun + you.power) {
			win(me, you);
		}
		else if (me.gun + me.power < you.gun + you.power) {
			win(you, me);
		}
		else if (me.gun + me.power == you.gun + you.power) {
			if (me.power > you.power) {
				win(me, you);
			} // 두 초기값 같다는 조건 없음?
			else if (me.power < you.power) {
				win(you, me);
			}
		}
	}


}

int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			pq[i][j].push(board[i][j]);
		}
	}
	int x, y, d, s;
	persons.push_back({0,0,0,0,0,0,0});
	for (int i = 1; i <= M; i++)
	{
		cin >> x >> y >> d >> s;
		persons.push_back({ i,x-1,y-1,d,s,0,0});
		p_board[x - 1][y - 1] = i;

	}

	while (true) {
		if (K == 0) break;
		for (int i = 1; i <= M; i++)
		{
			move(persons[i]);
		}


		K--;
	}

	for (int i = 1; i <= M; i++)
	{
		cout <<  persons[i].point <<" ";
	}
}