[삼성기출/C++] 루돌프의 반란

 

https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion?&utm_source=clipboard&utm_medium=text

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

 

 빡구현중에 손꼽히는 복잡함을 가진 23년도 기출 "루돌프의 반란"을 풀어보았다. 이 문제가 복잡한 점은, "모든 이동"에 대해 모두 다른 로직을 작성해주어야 한다는 점이다. 이 경우에는 최대한 함수의 배치를 잘 해서 실수를 줄이는 것이 관건이라고 할 수 있다.

그렇다면 이 문제를 풀기 위한 함수를 하나씩 살펴보자.

 

1. 루돌프의 이동

 

 루돌프의 이동을 풀기 위해선 다음 3가지 로직을 작성해야 한다.

• 돌진할 산타를 결정하는 로직
• 그 산타에 최단 경로로 돌진하는 위치 찾기
• 만약 산타와 충돌한다면, 산타에 대한 충돌 로직 발동시키기

 우선 돌진할 산타를 결정하기 위해 산타와의 distance를 구하는 함수를 만들자. 다음과 같이 거리의 제곱을 구하면 문제에서 요구하는 거리가 된다. 다른 문제에서는 norm-1 distance ( |x1-x2| + |x2-y2|) 를 구하라고 하는 경우도 있으므로 주의하자.

int calc(int deer_y, int deer_x, int sy, int sx) {
	return abs(deer_y - sy) * abs(deer_y - sy) + abs(deer_x - sx) * abs(deer_x - sx);
}

 

 그리고 돌진하려고 하는 산타를 결정하기 위해 그냥 무식하게 조건문을 작성했다. struct 선언하고 compare 함수 만들기가 귀찮기 때문이었다.

	for (int i = 1; i <= p; i++) {
		if (s[i].state == -1) continue;
		int sy = s[i].y, sx = s[i].x;
		int dist = calc(deer_y, deer_x, sy, sx);
		if (min_dist > dist || (min_dist == dist && min_sy < sy) || (min_dist == dist && min_sy == sy && min_sx < sx)) {
			min_dist = dist; min_sy = sy; min_sx = sx;
		}
	}

 

 여기에서 s[i].state == -1 은 해당 i의 산타가 죽었다는 표시이므로 건너뛴다. 산타를 찾았다면 비슷한 방식으로 최단경로로 돌진해주고, 만약 충돌이 일어난다면 다음과 같은 collision 함수로 보내준다.

	deer_y += dy[min_dir]; deer_x += dx[min_dir];
	if (land[deer_y][deer_x]) {
		int pid = land[deer_y][deer_x];
		s[pid].state = 2; // paralyzed
		collision(0, pid, min_dir); // {flag, pid, min_dir}
	}

 

 여기에서 산타 -> 루돌프 에 의한 충돌과, 루돌프 -> 산타 에 의한 충돌이 다른다는 점을 명심하자. 굉장히 귀찮지만, 그래도 이에 따라 충돌 거리 및 score 획득이 달라지므로 주의하자. 이를 flag로 설정해주고, 0이니깐 루돌프 -> 산타 충돌로 설정하고, collision 함수에서 해당 dir x C에 해당하는 만큼 이동시켜 준다. 이때 경계 처리를 해주고, 비었다면 함수를 종료시키고, 만약 다른 산타가 있어서 "상호작용" 이 일어난다면 다음 함수로 보내버리고, land를 업데이트한다. 

	s[pid].y = ny; s[pid].x = nx;
	land[y][x] = 0;
	if (is_out(ny, nx)) {
		s[pid].state = -1; return;
	}
	if (land[ny][nx] == 0) {
		land[ny][nx] = pid;
		return;
	}
	else { // 연쇄작용
		interaction(land[ny][nx], dir);
		land[ny][nx] = pid;
	}

 

 상호작용 함수의 다행스러운 점은, 산타끼리의 충돌에 대해서는 로직이 동일하다는 점이다. 따라서 다음과 같이 간단하게 interaction함수를 작성할 수 있다.

void interaction(int pid, int dir) {
	int y = s[pid].y, x = s[pid].x;
	int ny = y + dy[dir], nx = x + dx[dir];
	if (is_out(ny, nx)) {
		s[pid].state = -1; return;
	}
	s[pid].y = ny; s[pid].x = nx;
	if (land[ny][nx]) {
		interaction(land[ny][nx], dir);
	}
	land[ny][nx] = pid;
	return;
}

 

 

2. 산타의 이동

 

 산타의 이동을 진행할 때는 산타가 이동할 수 있는 방향이 상우하좌 4방향뿐임을 인지하고, 이에 따라 우선순위가 생긴다는 것을 명심하자. 이 우선순위 처리는 for 문을 돌리면 간단히 해결된다. 중요한것은 paralyzed 처리이다. 나는 산타의 turn이 올 때마다 state 가 양수라면 1씩 감소시키고, state 가 0이라면 move 하도록 로직을 세웠는데, 충돌에 대한 로직을 섬세하게 처리해야한다.

 

• 루돌프가 산타를 충돌했을 때 : 루돌프 이동 -> 산타 이동이 한 턴이므로, paralyzed state = 2 로 설정해야 2턴 후에 이동할 수 있음
• 산타가 산타를 충돌했을 때 : 다음 턴 루돌프 이동 -> 산타 이동 -> 루돌프 이동 -> 산타 이동 이때 이동할 수 있어야 하므로, paralyzed state = 1 로 설정

 debugging 하면서 코드의 진행 상태를 확인한다면 더 이해가 빠를 것이다.

 

 

 여기까지 작성했다면 문제를 풀 수 있다! 아래는 필자가 작성한 코드이다. print()함수를 주석 해제해서 디버깅하면서 확인하면 도움이 될 것이다.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void init() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); }

typedef struct santa {
	int state, y, x, score;
}Santa;

Santa s[34];
int land[54][54];
int n, m, p, c, d, pid, deer_y, deer_x, sy, sx;
const int dy[] = { -1,-1,0,1,1,1,0,-1 };
const int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dead_cnt;

int calc(int deer_y, int deer_x, int sy, int sx) {
	return abs(deer_y - sy) * abs(deer_y - sy) + abs(deer_x - sx) * abs(deer_x - sx);
}

bool is_out(int ny, int nx) {
	if (ny<1 || ny>n || nx<1 || nx>n) return true;
	return false;
}

void interaction(int pid, int dir) {
	int y = s[pid].y, x = s[pid].x;
	int ny = y + dy[dir], nx = x + dx[dir];
	if (is_out(ny, nx)) {
		s[pid].state = -1; return;
	}
	s[pid].y = ny; s[pid].x = nx;
	if (land[ny][nx]) {
		interaction(land[ny][nx], dir);
	}
	land[ny][nx] = pid;
	return;
}

void collision(int flag, int pid, int dir) {
	int y = s[pid].y, x = s[pid].x;
	int ny, nx;
	if (flag == 0) {
		ny = y + c * dy[dir];
		nx = x + c * dx[dir];
		s[pid].score += c;
	}
	else {
		ny = y + d * dy[dir];
		nx = x + d * dx[dir];
		s[pid].score += d;
	}
	s[pid].y = ny; s[pid].x = nx;
	land[y][x] = 0;
	if (is_out(ny, nx)) {
		s[pid].state = -1; return;
	}
	if (land[ny][nx] == 0) {
		land[ny][nx] = pid;
		return;
	}
	else { // 연쇄작용
		interaction(land[ny][nx], dir);
		land[ny][nx] = pid;
	}
}

void deer_move() {
	int min_dist = 1e9;
	int min_sy = -1, min_sx = -1;
	for (int i = 1; i <= p; i++) {
		if (s[i].state == -1) continue;
		int sy = s[i].y, sx = s[i].x;
		int dist = calc(deer_y, deer_x, sy, sx);
		if (min_dist > dist || (min_dist == dist && min_sy < sy) || (min_dist == dist && min_sy == sy && min_sx < sx)) {
			min_dist = dist; min_sy = sy; min_sx = sx;
		}
	}
	int min_dir = -1;
	for (int i = 0; i < 8; i++) {
		int ny = deer_y + dy[i], nx = deer_x + dx[i];
		if (is_out(ny, nx)) continue;
		int dist = calc(ny, nx, min_sy, min_sx);
		if (min_dist > dist) {
			min_dist = dist; min_dir = i;
		}
	}
	deer_y += dy[min_dir]; deer_x += dx[min_dir];
	if (land[deer_y][deer_x]) {
		int pid = land[deer_y][deer_x];
		s[pid].state = 2; // paralyzed
		collision(0, pid, min_dir); // {flag, pid, min_dir}
	}
}

void santa_move(int pid) {
	int min_dir = -1;
	int y = s[pid].y, x = s[pid].x;
	int min_dist = calc(deer_y, deer_x, y, x);
	for (int i = 0; i < 8; i += 2) {
		int ny = y + dy[i], nx = x + dx[i];
		if (is_out(ny, nx) || land[ny][nx]) continue;
		int dist = calc(deer_y, deer_x, ny, nx);
		if (min_dist > dist) {
			min_dist = dist; min_dir = i;
		}
	}
	if (min_dir == -1) return;
	int ny = y + dy[min_dir];
	int nx = x + dx[min_dir];
	if (ny == deer_y && nx == deer_x) {
		s[pid].state = 1; // paralyzed
		land[y][x] = 0;
		s[pid].y = ny; s[pid].x = nx;
		collision(1, pid, (min_dir + 4) % 8);
	}
	else {
		land[y][x] = 0;
		land[ny][nx] = pid;
		s[pid].y = ny;
		s[pid].x = nx;
	}
	return;
}

void print() {
	cout << "deer y : " << deer_y << " , " << "deer_x : " << deer_x << '\n';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == deer_y && j == deer_x) cout << 77 << ' ';
			else cout << land[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}


void go() {
	deer_move();
	for (int i = 1; i <= p; i++) {
		if (s[i].state == -1) continue;

		if (s[i].state > 0) s[i].state--;
		else if (s[i].state == 0) santa_move(i);
		//print();
	}
}


int main(){
	init();
	cin >> n >> m >> p >> c >> d;
	cin >> deer_y >> deer_x;
	for (int i = 0; i < p; i++) {
		cin >> pid >> sy >> sx;
		s[pid] = { 0,sy,sx,0 };
		land[sy][sx] = pid;
	}
	//print();
	for (int i = 0; i < m; i++) {
		go();
		if (dead_cnt == p) break;
		for (int i = 1; i <= p; i++) {
			if (s[i].state >= 0) s[i].score++;
		}
		/*for (int i = 1; i <= 4; i++) {
			cout << i << " : " << s[i].state << " " << s[i].y << " " << s[i].x << " " << s[i].score << '\n';
		}*/
	}
	for (int i = 1; i <= p; i++) {
		cout << s[i].score << ' ';
	}
	cout << '\n';
	return 0;
}

 

 이번 문제도 무난하게 첫 번째 시도에서 AC를 기록하였다.