코드트리 루돌프의 반란 (C++)

2023 삼성 하반기 코딩테스트 오후 1번 문제입니다. 기절된 산타에게 루돌프가 충돌하는 경우 다시 기절하도록 구현해야 하고 산타 이동시 거리가 줄어드는 방향으로 움직여야 합니다. 만약 거리가 줄어드는 방향이 없다면 그 자리에 가만히 있어야 합니다.

 

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	typedef tuple<int,int,int> tiii;
	const int INF=1e9+1;
	int N,M,P,C,D;
	int dx[]={-1,0,1,0,1,1,-1,-1};
	int dy[]={0,1,0,-1,1,-1,1,-1};
	vector<pii> santa;
	vector<int> death(30); // -1: death, 0: alive, k: stun
	vector<int> score(30);
	bool cmp(vector<int>& a, vector<int>& b) {
	// 산타 정렬
	if(a[0]==b[0]) {
	if(a[1]==b[1]) return a[2]>b[2];
	return a[1]>b[1];
	}
	return a[0]<b[0];
	}
	int dist(pii a, pii b) {
	return pow(a.first-b.first,2)+pow(a.second-b.second,2);
	}
	bool in_board(pii a) {
	if(a.first>0 && a.first<=N && a.second>0 && a.second<=N) return true;
	return false;
	}
	pii find_santa(pii a) {
	// 루돌프가 찾는 산타
	vector<vector<int>> d; // (index, (distance, r, c))
	for(int i=0;i<P;i++) {
	if(death[i]==-1) continue;
	pii b=santa[i];
	d.push_back({dist(a,b),b.first,b.second});
	}
	sort(d.begin(),d.end(),cmp);
	return {d[0][1],d[0][2]};
	}
	int check_santa(pii b, int me) {
	// b 좌표에 산타가 있는지 확인
	for(int i=0;i<=P;i++) {
	if(i==me) continue;
	if(santa[i].first==b.first && santa[i].second==b.second)
	return i;
	}
	return -1;
	}
	void rudolph_move(pii& a) {
	pii s=find_santa(a);
	vector<pii> v;
	for(int i=0;i<8;i++) {
	int nx=a.first+dx[i], ny=a.second+dy[i];
	int d=dist({nx,ny},s);
	v.push_back({d,i});
	}
	sort(v.begin(),v.end());
	a.first+=dx[v[0].second], a.second+=dy[v[0].second];
	int r=check_santa(a,-1); // 산타가 없다면 -1
	if(r!=-1) { // 충돌: rudolph -> santa
	score[r]+=C;
	santa[r].first+=C*dx[v[0].second], santa[r].second+=C*dy[v[0].second];
	death[r]=2; // stun
	if(in_board(santa[r])) {
	// santa interaction
	int target=check_santa(santa[r],r);
	while(target!=-1) {
	santa[target].first+=dx[v[0].second], santa[target].second+=dy[v[0].second];
	if(!in_board(santa[target])) death[target]=-1;
	target=check_santa(santa[target],target);
	}
	}
	else death[r]=-1;
	}
	}
	int find_rudolph(pii b, pii a) {
	// 산타가 찾는 루돌프
	// 반드시 거리가 줄어야 한다
	vector<pii> v;
	int cur_dist=dist(b,a);
	for(int i=0;i<4;i++) {
	int nx=b.first+dx[i], ny=b.second+dy[i];
	if(in_board({nx,ny}) && check_santa({nx,ny},-1)==-1) {
	int d=dist({nx,ny},a);
	if(cur_dist>d) v.push_back({d,i});
	}
	}
	if(v.empty()) return -1;
	sort(v.begin(),v.end());
	return v[0].second;
	}
	void santa_move(pii R) {
	for(int i=0;i<P;i++) {
	if(death[i]) continue;
	int dir=find_rudolph(santa[i],R);
	if(dir==-1) continue;
	santa[i].first+=dx[dir], santa[i].second+=dy[dir];
	if(R.first==santa[i].first && R.second==santa[i].second) { // santa -> rudolph
	score[i]+=D;
	int dir2=dir+2>3 ? dir-2 : dir+2;
	death[i]=2; // stun
	santa[i].first+=D*dx[dir2], santa[i].second+=D*dy[dir2];
	if(in_board(santa[i])) {
	// santa interaction
	int target=check_santa(santa[i],i);
	while(target!=-1) {
	santa[target].first+=dx[dir2], santa[target].second+=dy[dir2];
	if(!in_board(santa[target])) death[target]=-1;
	target=check_santa(santa[target],target);
	}
	}
	else death[i]=-1;
	}
	}
	}
	void turn_end() {
	for(int i=0;i<P;i++) {
	if(death[i]!=-1) score[i]+=1;
	}
	}
	void recovery() {
	for(int i=0;i<P;i++) {
	if(death[i]>0) death[i]-=1;
	}
	}
	bool retire() {
	for(int i=0;i<P;i++) if(death[i]!=-1) return false;
	return true;
	}
	int main() {
	fastio
	//freopen("input.txt","r",stdin);
	cin>>N>>M>>P>>C>>D;
	pii R; cin>>R.first>>R.second;
	santa=vector<pii>(P);
	for(int i=0;i<P;i++) {
	int pn,sr,sc; cin>>pn>>sr>>sc;
	santa[pn-1]={sr,sc};
	}
	for(int i=0;i<M;i++) {
	if(retire()) break;
	recovery();
	rudolph_move(R);
	santa_move(R);
	turn_end();
	}
	for(int i=0;i<P;i++) cout<<score[i]<<' ';
	return 0;
	}

view raw codetree_santa.cpp hosted with ❤ by GitHub