문제

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

---

입력

첫 번째 줄에 N, M, P, C, D가 공백을 사이에 두고 주어집니다.
다음 줄에는 루돌프의 초기 위치가 주어집니다.
다음 P개 줄에 걸쳐 산타의 번호, 초기위치가 주어집니다.

---

출력

게임이 끝났을 때 각 산타가 얻은 최종 점수를 1번부터 P번까지 순서대로 공백을 사이에 두고 출력합니다.

---

풀이

제한조건

N: 게임판의 크기 (3≤N≤50)
M: 게임 턴 수 (1≤M≤1000)
P: 산타의 수 (1≤P≤30)
C: 루돌프의 힘 (1≤C≤N)
D: 산타의 힘 (1≤D≤N)

접근방법

시뮬레이션

침착하게 풀지 않으면 풀이 시간이 끝도 없이 늘어난다.
더군다나 문제의 설명을 정확하게 보고 이해해야한다.

차근차근 살펴보자.

크게 4가지의 기능을 구현하면 된다.

1. 게임판 구성
2. 루돌프 이동
3. 산타 이동
4. 충돌 처리

1. 게임판 구성
입력으로 주어지는 것을 적절히 저장하자.
입력값이외에도 각 산타의 생존여부와 점수를 담을 변수가 더 필요하다.

2. 루돌프 이동
루돌프는 8가지 방향으로 이동가능하다.
또한 가장 가까운 산타가 여럿 존재할 경우, 조건에 맞게 잘 찾아가야한다.

이동 자체는 단순하다.
다만 충돌처리 부분을 조금 신경써야한다.
충돌 처리는 이후에 다시 살펴보자.

3. 산타 이동
산타는 4가지 방향으로 이동가능하다.
이동 가능한 방향이 2개 이상이라면, 상우하좌의 우선순위를 가진다.
여기서 문제를 잘 읽어야 한다.

이동할 수 있는 구역이 있더라도, 루돌프로부터 멀어지는 위치면 이동하지 않는다.
주의하자

탈락한 산타는 더 이상 사용되지 않는다.

4. 충돌 처리
루돌프-산타간의 충돌이 발생하면 산타의 이동이 발생한다.
여기서 주의할 점은 산타가 도착할 위치에 다른 산타가 있다면
해당 산타도 1칸 밀려난다는 점이다.

주의할 점은, 루돌프는 산타의 기절 여부와 상관없이 가장 가까운 산타와 충돌한다.
산타는 기절상태일 경우, 자의에 의해서 움직이지 않음을 주의하자.

중간 경로에 위치한 산타는 아무런 상관이 없다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M, P, C, D;
	static int[][] arr;
	static int[] scores, remainStun;
	static int numSanta;
	static int rx, ry;

	static class Santa {
		int x;
		int y;
		boolean isOut;
	}

	static Santa[] santas;

	// numpad 기준, 86249317 순
	static int[] dx = {-1, 0, 1, 0, -1, 1, 1, -1};
	static int[] dy = {0, 1, 0, -1, 1, 1, -1, -1};

	public static void main(String[] args) throws Exception {
		// input
		init();

		while (M-- > 0) {
			if (numSanta < 1)
				break;
			int santaIdx = findNearSanta();
			int deerDir = getDeerDirection(santaIdx);

			// 루돌프 이동
			moveDeer(deerDir);

			// 산타 이동
			for (int i = 1; i <= P; ++i) {
				remainStun[i]--;

				// 이미 아웃된 산타
				if (santas[i].isOut)
					continue;
				// 충돌하여 정지 상태
				if (remainStun[i] > 0) {
					continue;
				}

				boolean flag = false;
				int dir = -1;
				int mindist = Integer.MAX_VALUE;
				int base = getDistance(rx, ry, santas[i].x, santas[i].y);
				for (int d = 0; d < 4; ++d) {
					int nextX = santas[i].x + dx[d];
					int nextY = santas[i].y + dy[d];
					if (!isInRange(nextX, nextY))
						continue;

					// 다음칸이 루돌프
					if (arr[nextX][nextY] == 99) {
						flag = true;
						arr[santas[i].x][santas[i].y] = 0;
						santas[i].x = nextX;
						santas[i].y = nextY;
						scores[i] += D;
						remainStun[i] = 2;
						moveSanta(i, (d + 2) % 4, D);
						arr[nextX][nextY] = 99;
						break;
					}

					// 다음칸이 비어있음
					if (arr[nextX][nextY] == 0) {
						int dist = getDistance(rx, ry, nextX, nextY);
						if(dist >= base)
							continue;
						if (mindist > dist) {
							mindist = dist;
							dir = d;
						}
					}
				}
				if (!flag && dir != -1)
					moveSanta(i, dir, 1);
			}

			// 생존 산타
			for (int i = 1; i <= P; ++i) {
				if (santas[i].isOut)
					continue;
				scores[i]++;
			}
		}
		// output
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= P; ++i)
			sb.append(scores[i]).append(" ");
		System.out.println(sb);
	}

	private static void moveSanta(int idx, int dir, int step) {
		arr[santas[idx].x][santas[idx].y] = 0;
		int nextX = santas[idx].x + dx[dir] * step;
		int nextY = santas[idx].y + dy[dir] * step;

		// 이동하면 밖으로 떨어진다
		if (!isInRange(nextX, nextY)) {
			santas[idx].isOut = true;
			numSanta--;
			return;
		}
		if (arr[nextX][nextY] != 0) {
			// 다른 산타도 밀려야 한다.
			int nextIdx = arr[nextX][nextY];
			moveSanta(nextIdx, dir, 1);
		}
		santas[idx].x = nextX;
		santas[idx].y = nextY;
		arr[nextX][nextY] = idx;
	}

	private static void moveDeer(int dir) {
		int nextX = rx + dx[dir];
		int nextY = ry + dy[dir];
		if (arr[nextX][nextY] != 0) {
			int idx = arr[nextX][nextY];
			remainStun[idx] = 3;
			scores[idx] += C;
			moveSanta(idx, dir, C);
		}
		arr[nextX][nextY] = arr[rx][ry];
		arr[rx][ry] = 0;
		rx = nextX;
		ry = nextY;
	}

	private static int getDeerDirection(int santaIdx) {
		int sx = santas[santaIdx].x;
		int sy = santas[santaIdx].y;
		if (rx > sx) {
			if (ry > sy)
				return 7;
			if (ry < sy)
				return 4;
			return 0;
		}
		if (rx < sx) {
			if (ry > sy)
				return 6;
			if (ry < sy)
				return 5;
			return 2;
		}
		if (ry > sy)
			return 3;
		if (ry < sy)
			return 1;

		return -1;
	}

	private static int findNearSanta() {
		int min = Integer.MAX_VALUE;
		int idx = 0;
		for (int i = 1; i <= P; ++i) {
			if (santas[i].isOut)
				continue;

			int dist = getDistance(rx, ry, santas[i].x, santas[i].y);
			if (min > dist) {
				min = dist;
				idx = i;
			} else if (min == dist) {
				if (santas[idx].x < santas[i].x) {
					min = dist;
					idx = i;
				} else if (santas[idx].x == santas[i].x) {
					if (santas[idx].y < santas[i].y) {
						min = dist;
						idx = i;
					}
				}
			}
		}
		return idx;
	}

	private static void init() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);
		P = stoi(inputs[2]);
		C = stoi(inputs[3]);
		D = stoi(inputs[4]);

		arr = new int[N + 1][N + 1];
		remainStun = new int[P+ 1];
		scores = new int[P + 1];
		santas = new Santa[P + 1];
		santas[0] = new Santa();
		for (int i = 0; i <= P; ++i)
			santas[i] = new Santa();

		inputs = in.readLine().split(" ");
		rx = stoi(inputs[0]);
		ry = stoi(inputs[1]);
		arr[rx][ry] = 99;
		for (int i = 0; i < P; ++i) {
			inputs = in.readLine().split(" ");
			int num = stoi(inputs[0]);
			santas[num].x = stoi(inputs[1]);
			santas[num].y = stoi(inputs[2]);
			arr[santas[num].x][santas[num].y] = num;
			numSanta++;
		}
	}

	public static int getDistance(int x1, int y1, int x2, int y2) {
		return ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1));
	}

	public static boolean isInRange(int x, int y) {
		if (0 < x && x <= N && 0 < y && y <= N)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}