루돌프의 반란

Simulation

평균 : 180'

---

sol : 108' 5''

• 수행 시간 : 7ms
• 메모리 : 0MB

Learnings

• 처음 풀었을 때는 9ms였는데 이번에 7ms가 나왔다.
• 상태관리를 적재적소에서 잘한 것 같다.
• 재귀가 약점이었는데 상태 관리를 위한 분기를 명확하게 처리했다.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// 1-based
const int MAX_N = 51;
const int RUDOLP = -1;
const int EMPTY = 0;
int n, m, p, c, d;
int turn;
const int ds[8][2] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
	{-1, -1},
	{-1, 1},
	{1, -1},
	{1, 1}
};

struct Santa {
	int r;
	int c;
	int stun;
	bool onGrid;
	int score;

	Santa() { }
};

struct Rudolp {
	int r;
	int c;

	Rudolp() :
		r(-1), c(-1) { }
};

vector<Santa> santas;
Rudolp rudolp;
int grid[MAX_N][MAX_N];

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == RUDOLP) cout << 'R' << ' ';
			else cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl << endl;
}

void Init() {
	cin >> n >> m >> p >> c >> d;
	
	cin >> rudolp.r >> rudolp.c;
	grid[rudolp.r][rudolp.c] = RUDOLP;
	
	santas.resize(p + 1);
	for (int i = 1; i <= p; i++) {
		int id, r, c;
		cin >> id >> r >> c;
		santas[id].r = r, santas[id].c = c, santas[id].score = 0;
		santas[id].onGrid = true, santas[id].stun = 0;

		grid[r][c] = id;
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

int Dist(int r1, int c1, int r2, int c2) {
	return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}

void Correlation(int id, int dir) {
	int ni = santas[id].r + ds[dir][0];
	int nj = santas[id].c + ds[dir][1];

	if (!InGrid(ni, nj)) {
		santas[id].onGrid = false;
		return;
	}

	santas[id].r = ni, santas[id].c = nj;

	if (grid[ni][nj] > 0) {
		int nextId = grid[ni][nj];
		grid[ni][nj] = id;
		Correlation(nextId, dir);
		return;
	}

	if (grid[ni][nj] == EMPTY) {
		grid[ni][nj] = id;
		return;
	}
}

void CollideRtoS(int id, int dir) {
	santas[id].score += c;
	santas[id].stun = turn + 2;

	int ni = santas[id].r + ds[dir][0] * c;
	int nj = santas[id].c + ds[dir][1] * c;

	if (!InGrid(ni, nj)) {
		santas[id].onGrid = false;
		return;
	}

	santas[id].r = ni, santas[id].c = nj;

	if (grid[ni][nj] > 0) {
		int nextId = grid[ni][nj];
		grid[ni][nj] = id;
		Correlation(nextId, dir);
		return;
	}

	if (grid[ni][nj] == EMPTY) {
		grid[ni][nj] = id;
		return;
	}
}

void RudolpMove() {
	int minDist = INT_MAX;
	// r-max, c-max, id
	vector<tuple<int, int, int>> targets;
	for (int s = 1; s <= p; s++) {
		if (!santas[s].onGrid) continue;

		int curDist = Dist(rudolp.r, rudolp.c, santas[s].r, santas[s].c);
		if (curDist < minDist) {
			minDist = curDist;
			targets.clear();
			targets.push_back(make_tuple(-santas[s].r, -santas[s].c, s));
		}
		else if (curDist == minDist) {
			targets.push_back(make_tuple(-santas[s].r, -santas[s].c, s));
		}
	}
	sort(targets.begin(), targets.end());

	int bestDist = INT_MAX, best_ni = -1, best_nj = -1, best_dir = -1;
	int ti, tj, tid;
	tie(ti, tj, tid) = targets[0];
	ti *= -1, tj *= -1;

	for (int d = 0; d < 8; d++) {
		int ni = rudolp.r + ds[d][0], nj = rudolp.c + ds[d][1];
		if (!InGrid(ni, nj)) continue;

		int curDist = Dist(ni, nj, ti, tj);
		if (curDist < bestDist) {
			bestDist = curDist;
			best_ni = ni, best_nj = nj;
			best_dir = d;
		}
	}

	grid[rudolp.r][rudolp.c] = EMPTY;
	rudolp.r = best_ni, rudolp.c = best_nj;
	if (grid[rudolp.r][rudolp.c] != EMPTY) {
		int nextId = grid[rudolp.r][rudolp.c];
		grid[rudolp.r][rudolp.c] = RUDOLP;
		CollideRtoS(nextId, best_dir);
	}
	else {
		grid[rudolp.r][rudolp.c] = RUDOLP;
	}
}

void CollideStoR(int id, int dir) {
	santas[id].score += d;
	santas[id].stun = turn + 2;
	int opposDir = (dir + 2) % 4;

	int ni = santas[id].r + ds[opposDir][0] * d;
	int nj = santas[id].c + ds[opposDir][1] * d;

	if (!InGrid(ni, nj)) {
		santas[id].onGrid = false;
		return;
	}

	santas[id].r = ni, santas[id].c = nj;
	if (grid[ni][nj] > 0) {
		int nextId = grid[ni][nj];
		grid[ni][nj] = id;
		Correlation(nextId, opposDir);
		return;
	}

	if (grid[ni][nj] == EMPTY) {
		grid[ni][nj] = id;
		return;
	}
}

void SantasMove() {
	for (int s = 1; s <= p; s++) {
		// 탈락한 산타는 움직이지 않음.
		if (!santas[s].onGrid) continue;
		// k턴에서 기절한 산타는 k+1턴까지는 움직이지 않음.
		if (santas[s].stun > turn) continue;
		
		int ci = santas[s].r, cj = santas[s].c;
		int bestDist = Dist(rudolp.r, rudolp.c, ci, cj);
		int best_i = -1, best_j = -1, best_dir = -1;

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (grid[ni][nj] > 0) continue;
			int curDist = Dist(rudolp.r, rudolp.c, ni, nj);
			if (curDist < bestDist) {
				bestDist = curDist;
				best_i = ni, best_j = nj, best_dir = d;
			}
		}
		// 가까워질 수 있는 방법이 없다면 움직이지 않는다.
		if (best_i == -1) continue;

		grid[ci][cj] = EMPTY;
		santas[s].r = best_i, santas[s].c = best_j;
		if (grid[santas[s].r][santas[s].c] == RUDOLP) {
			CollideStoR(s, best_dir);
		}
		else {
			grid[santas[s].r][santas[s].c] = s;
		}
	}
}

bool Finish() {
	for (int s = 1; s <= p; s++) {
		if (santas[s].onGrid) return false;
	}
	return true;
}

void PrintScore() {
	for (int s = 1; s <= p; s++) {
		cout << santas[s].score << ' ';
	}
	cout << endl;
}

void Salary() {
	for (int s = 1; s <= p; s++) {
		if (!santas[s].onGrid) continue;
		santas[s].score++;
	}
}

int main() {
	Init();

	while(++turn <= m) {
		RudolpMove();

		SantasMove();

		if (Finish()) break;

		Salary();
	}

	PrintScore();

	return 0;
}