루돌프의 반란

Simulation

평균 : 180'

---

sol : 137' 33''

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

Learings

• 항상 페이즈 덩어리별로 주어지는 건 아니니까 문제 유형에 익숙해졌다고 대충 읽지 말자!!!

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

#define MAX_N 51
#define RUDOLP -1

using namespace std;


// p : s_num, c : r_power, d : s_power
int n, m, s_num, r_power, s_power;
// 게임 전체 턴 관리
int turn;
// 상 우 하 좌 |
int ds[8][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };

struct Rudolp {
	int r;
	int c;
	int power;
	int dir;

	Rudolp () {}
	Rudolp(int _r, int _c, int _dir, int _power) :
		r(_r), c(_c), dir(_dir), power(_power) { }
};

struct Santa {
	int r;
	int c;
	// 0으로 시작, 기절할 경우 기절한 턴+1 입력.
	int stunnedTurn;
	int score;
	int dir;
	bool isOut;

	Santa () {}
	Santa(int _r, int _c, int _stunnedTurn, int _score, int _dir, bool _isOut) :
		r(_r), c(_c), stunnedTurn(_stunnedTurn), score(_score), dir(_dir), isOut(_isOut) { }
};

Rudolp rudolp;
vector<Santa> santas;

bool InGrid(int r, int c) {
	return 1 <= r && r <= n && 1 <= c && c <= n;
}

void Init() {
	cin >> n >> m >> s_num >> r_power >> s_power;

	int rr, rc;
	cin >> rr >> rc;
	rudolp = Rudolp(rr, rc, r_power, -1);

	santas.resize(s_num + 1);

	for (int s = 1; s <= s_num; s++) {
		int sid, sr, sc;
		cin >> sid >> sr >> sc;
		santas[sid] = Santa(sr, sc, 0, 0, -1, false);
	}
}

int RudolpToSantaDist(int sr, int sc, int rr, int rc) {
	return (sr - rr) * (sr - rr) + (sc - rc) * (sc - rc);
}

void SantaOut(int s) {
	santas[s].isOut = true;
}

void UpdateRudolp(int nr, int nc, int nd) {
	rudolp.r = nr;
	rudolp.c = nc;
	rudolp.dir = nd;
}

void UpdateSanta(int s, int nr, int nc, int nd) {
	// 그리드 업데이트
	//grid[santas[s].r][santas[s].c] = 0;
	// 이 때, 루돌프 정보는 그리드에서 덮어씌워짐 (Debug 필요)
	//grid[nr][nc] = s;

	// 구조체 업데이트
	santas[s].r = nr;
	santas[s].c = nc;
	santas[s].dir = nd;
}

int ChooseSanta() {
	// 가장 가까운 산타를 찾아서
	int targetSanta = -1;
	int shortestDist = INT_MAX;
	for (int s = 1; s <= s_num; s++) {
		if (!santas[s].isOut) {
			int curDist = RudolpToSantaDist(santas[s].r, santas[s].c, rudolp.r, rudolp.c);
			bool isCloser = false;
			// 처음 만난 산타라면
			if (targetSanta == -1) {
				isCloser = true;
			}
			// 거리가 더 짧다면
			if (shortestDist > curDist) {
				isCloser = true;
			}
			// 거리가 같다면
			else if (shortestDist == curDist) {
				// r 좌표가 더 큰 산타
				if (santas[s].r > santas[targetSanta].r) {
					isCloser = true;
				}
				// r 좌표도 같다면
				else if (santas[s].r == santas[targetSanta].r) {
					// c 좌표가 더 큰 산타
					if (santas[s].c > santas[targetSanta].c) {
						isCloser = true;
					}
				}
			}

			if (isCloser) {
				shortestDist = curDist;
				targetSanta = s;
			}
		}
	}

	return targetSanta;
}

void RudolpMove(int s) {
	int shortestDist = INT_MAX;
	int next_r = -1, next_c = -1, next_dir = -1;

	// 8방향중 가장 가까워지는 방향을 찾아서
	for (int d = 0; d < 8; d++) {
		int nrr = rudolp.r + ds[d][0], nrc = rudolp.c + ds[d][1];
		if (InGrid(nrr, nrc)) {
			int curDist = RudolpToSantaDist(santas[s].r, santas[s].c, nrr, nrc);
			if (curDist < shortestDist) {
				shortestDist = curDist;
				next_r = nrr, next_c = nrc, next_dir = d;
			}
		}
	}

	// 루돌프의 다음 위치 정보 업데이트
	UpdateRudolp(next_r, next_c, next_dir);
}

void SideEffect(int s, int dir) {
	int nsr = santas[s].r + ds[dir][0], nsc = santas[s].c + ds[dir][1];

	UpdateSanta(s, nsr, nsc, dir);

	// 상호작용으로 인해 밖으로 밀려나간 경우
	if (!InGrid(santas[s].r, santas[s].c)) {
		SantaOut(s);
		return;
	}

	// 상호작용으로 인해 다른 산타를 밀친 경우
	for (int ns = 1; ns <= s_num; ns++) {
		if (ns == s || santas[ns].isOut) continue;

		if (santas[ns].r == santas[s].r && santas[ns].c == santas[s].c) {
			SideEffect(ns, santas[s].dir);
		}
	}
}

void ColRudToSan() {
	// 루돌프가 산타를 밀친 경우
	for (int s = 1; s <= s_num; s++) {
		if (rudolp.r == santas[s].r && rudolp.c == santas[s].c) {
			santas[s].score += r_power;
			santas[s].stunnedTurn = turn + 1;

			int nsr = santas[s].r + r_power * ds[rudolp.dir][0];
			int nsc = santas[s].c + r_power * ds[rudolp.dir][1];

			UpdateSanta(s, nsr, nsc, rudolp.dir);

			// 밀려난 위치가 바깥이라면
			if (!InGrid(santas[s].r, santas[s].c)) {
				// 산타는 게임에서 탈락.
				SantaOut(s);
			}
			else {
				for (int ns = 1; ns <= s_num; ns++) {
					if (ns == s || santas[ns].isOut) continue;

					// 밀려난 위치에 다른 산타가 있다면 상호작용 발생
					if (santas[ns].r == santas[s].r && santas[ns].c == santas[s].c) {
						SideEffect(ns, santas[s].dir);
					}
				}
			}
		}
	}
}

void ColSanToRud() {
	// 산타가 루돌프에게 박은 경우
	for (int s = 1; s <= s_num; s++) {
		if (rudolp.r == santas[s].r && rudolp.c == santas[s].c) {
			santas[s].score += s_power;
			santas[s].stunnedTurn = turn + 1;

			int opposite = (santas[s].dir + 2) % 4;
			int nsr = santas[s].r + s_power * ds[opposite][0];
			int nsc = santas[s].c + s_power * ds[opposite][1];

			UpdateSanta(s, nsr, nsc, opposite);


			// 밀려난 위치가 바깥이라면
			if (!InGrid(santas[s].r, santas[s].c)) {
				// 산타는 게임에서 탈락.
				SantaOut(s);
			}
			else {
				for (int ns = 1; ns <= s_num; ns++) {
					if (ns == s || santas[ns].isOut) continue;

					// 밀려난 위치에 다른 산타가 있다면 상호작용 발생
					if (santas[ns].r == santas[s].r && santas[ns].c == santas[s].c) {
						SideEffect(ns, santas[s].dir);
					}
				}
			}
		}
	}
}

void RudolpTurn() {
	// 0. 가장 가까운 산타 설정
	int targetSanta = ChooseSanta();
	if (targetSanta == -1) return;
	
	// 1. 산타를 향해 1칸 돌진
	RudolpMove(targetSanta);

	// 2. Collide Check (Rudolp to Santa)
	ColRudToSan();
}

void SantaMove() {
	for (int s = 1; s <= s_num; s++) {
		// 게임에서 탈락했거나 기절한 산타는 움직일 수 없다.
		if (santas[s].isOut || santas[s].stunnedTurn >= turn) continue;

		int next_r = -1, next_c = -1, next_d = -1;
		// 현재 산타 위치 ~ 루돌프 거리
		int shortest = RudolpToSantaDist(santas[s].r, santas[s].c, rudolp.r, rudolp.c);

		for (int d = 0; d < 4; d++) {
			int nsr = santas[s].r + ds[d][0], nsc = santas[s].c + ds[d][1];
			bool isPossible = true;

			// 게임판 밖이나 다른 산타가 있는 칸은 움직일 수 없다.
			if (!InGrid(nsr, nsc)) continue;
			// 다른 산타가 있을 경우 움직일 수 없다.
			for (int ns = 1; ns <= s_num; ns++) {
				if (ns == s || santas[ns].isOut) continue;
				if (santas[ns].r == nsr && santas[ns].c == nsc) {
					isPossible = false;
					break;
				}
			}
			if (!isPossible) continue;


			int curDist = RudolpToSantaDist(nsr, nsc, rudolp.r, rudolp.c);
			if (curDist < shortest) {
				shortest = curDist;
				next_r = nsr, next_c = nsc, next_d = d;
			}
		}

		// 움직일 수 있는 칸이 없거나, 있어도 루돌프로부터 가까워질 수 있는 방법이 없다면
		// 산타는 움직이지 않는다.
		if (next_r == -1) continue;

		// 그게 아니면 산타는 움직인다.
		UpdateSanta(s, next_r, next_c, next_d);

		// Collide Check
		ColSanToRud();
	}
}

void SantaTurn() {
	// 1. Santa Move
	SantaMove();
}

bool FinishCheck() {
	for (int s = 1; s <= s_num; s++) {
		if (!santas[s].isOut) return false;
	}

	return true;
}

void GiveBonus() {
	for (int s = 1; s <= s_num; s++) {
		if (!santas[s].isOut) santas[s].score++;
	}
}

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

int main() {
	Init();

	while (++turn <= m) {
		// 1. Rudolpt Move
		RudolpTurn();

		// 게임 종료 체크
		if (FinishCheck()) break;

		// 2. Santa Move
		SantaTurn();

		// 게임 종료 체크
		if (FinishCheck()) break;

		// 3. 생존 산타들에게 1점씩 부여
		GiveBonus();
	}

	PrintAnswer();

	return 0;
}