1번부터 번까지 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!
(1) 게임판의 구성
- 게임판은 크기의 격자로 이루어져 있습니다. 각 위치는 의 형태로 표현되며, 아래로 갈수록 이 증가, 오른쪽으로 갈수록 가 증가합니다. 좌상단은 입니다.
- 게임은 총 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.
- 게임판에서 두 칸 , 사이의 거리는 으로 계산됩니다.
(2) 루돌프의 움직임
- 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다. 단, 게임에서 탈락하지 않은 산타 중 가장 가까운 산타를 선택해야 합니다.
- 만약 가장 가까운 산타가 2명 이상이라면, 좌표가 큰 산타를 향해 돌진합니다. 이 동일한 경우, 좌표가 큰 산타를 향해 돌진합니다.
- 루돌프는 상하좌우, 대각선을 포함한 인접한 8방향 중 하나로 돌진할 수 있습니다. (편의상 인접한 대각선 방향으로 전진하는 것도 1칸 전진하는 것이라 생각합니다.) 가장 우선순위가 높은 산타를 향해 8방향 중 가장 가까워지는 방향으로 한 칸 돌진합니다.
(3) 산타의 움직임
- 산타는 1번부터 번까지 순서대로 움직입니다.
- 기절했거나 이미 게임에서 탈락한 산타는 움직일 수 없습니다.
- 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.
- 산타는 다른 산타가 있는 칸이나 게임판 밖으로는 움직일 수 없습니다.
- 움직일 수 있는 칸이 없다면 산타는 움직이지 않습니다.
- 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타는 움직이지 않습니다.
- 산타는 상하좌우로 인접한 4방향 중 한 곳으로 움직일 수 있습니다. 이때 가장 가까워질 수 있는 방향이 여러 개라면, 상우하좌 우선순위에 맞춰 움직입니다.
(4) 충돌
- 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다.
- 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해온 방향으로 칸 만큼 밀려나게 됩니다.
- 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해온 반대 방향으로 칸 만큼 밀려나게 됩니다.
- 밀려나는 것은 포물선 모양을 그리며 밀려나는 것이기 때문에 이동하는 도중에 충돌이 일어나지는 않고 정확히 원하는 위치에 도달하게 됩니다.
- 만약 밀려난 위치가 게임판 밖이라면 산타는 게임에서 탈락됩니다.
- 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용이 발생합니다.
(5) 상호작용
- 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다.
- 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다. 그 옆에 산타가 있다면 연쇄적으로 1칸씩 밀려나는 것을 반복하게 됩니다. 게임판 밖으로 밀려나오게 된 산타의 경우 게임에서 탈락됩니다.
(6) 기절
- 산타는 루돌프와의 충돌 후 기절을 하게 됩니다. 현재가 번째 턴이었다면, 번째 턴까지 기절하게 되어 번째 턴부터 다시 정상상태가 됩니다.
- 기절한 산타는 움직일 수 없게 됩니다. 단, 기절한 도중 충돌이나 상호작용으로 인해 밀려날 수는 있습니다.
- 루돌프는 기절한 산타를 돌진 대상으로 선택할 수 있습니다.
(7) 게임 종료
- 번의 턴에 걸쳐 루돌프, 산타가 순서대로 움직인 이후 게임이 종료됩니다.
- 만약 명의 산타가 모두 게임에서 탈락하게 된다면 그 즉시 게임이 종료됩니다.
- 매 턴 이후 아직 탈락하지 않은 산타들에게는 1점씩을 추가로 부여합니다.
게임이 끝났을 때 각 산타가 얻은 최종 점수를 구하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에 , , , , 가 공백을 사이에 두고 주어집니다.
다음 줄에는 루돌프의 초기 위치 가 주어집니다.
다음 개의 줄에 걸쳐서 산타의 번호 과 초기 위치 가 공백을 사이에 두고 주어집니다.
처음 산타와 루돌프의 위치는 겹쳐져 주어지지 않음을 가정해도 좋습니다.
- : 게임판의 크기 ()
- : 게임 턴 수 ()
- : 산타의 수 ()
- : 루돌프의 힘 ()
- : 산타의 힘 ()
- : 산타의 번호 ()
- : 루돌프의 초기 위치 ()
- : 산타의 초기 위치 ()
출력 형식
게임이 끝났을 때 각 산타가 얻은 최종 점수를 1번부터 번까지 순서대로 공백을 사이에 두고 출력합니다.
입출력 예제
예제1
입력:
5 7 4 2 2
3 2
1 1 3
2 3 5
3 5 1
4 4 4출력:
11 6 2 7예제2
입력:
5 10 5 1 2
5 5
2 1 4
1 3 2
4 2 4
5 1 3
3 5 3
출력:
8 14 15 12 12
정답 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, M, P, C, D, rx, ry;
static int[][] map;
static List<Santa> list = new ArrayList<>(); // 인덱스 순서대로 산타 위치 저장
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken()); // 게임판 크기
M = Integer.parseInt(st.nextToken()); // 게임 턴 수
P = Integer.parseInt(st.nextToken()); // 산타 수
C = Integer.parseInt(st.nextToken()); // 루돌프 힘
D = Integer.parseInt(st.nextToken()); // 산타 힘
map = new int[N+1][N+1]; // 게임판
st = new StringTokenizer(br.readLine());
ry = Integer.parseInt(st.nextToken());
rx = Integer.parseInt(st.nextToken());
map[ry][rx] = -1; // 루돌프 위치 -1로 저장
list.add(new Santa(0, 0,0,0,-2)); // 인덱스 맞추기용 데이터
for (int i = 0; i < P; i++) { // 게임판에 산타 인덱스로 각 산타 위치 저장
st = new StringTokenizer(br.readLine());
int pi = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
map[y][x] = pi; // 산타 위치 저장
list.add(new Santa(pi, y, x, 0, -2));
}
Collections.sort(list);
for (int turn = 1; turn <= M; turn++) { // M번 진행
moveRudolf(turn); // 루돌프 움직이기
refreshMap(); //맵 업데이트
//2. 산타 움직임
for (int s = 1; s <= P; s++) { // 순서대로
int y = list.get(s).y;
int x = list.get(s).x;
int canMove = list.get(s).canMove; // 기절한 턴
if (isRange(y, x)) { // 탈락하지 않은 산타 체크
if (canMove == -2 || turn-canMove == 2) {
list.get(s).canMove = -2;
moveSanta(s, turn); // 현재 턴 이동 금지가 아닐 경우
}
refreshMap();
}
}
// 산타가 맵에 남아있는지 확인
int sCnt = 0;
for (int s = 1; s <= P; s++) {
Santa tmp = list.get(s);
if (isRange(tmp.y, tmp.x)) {
sCnt++;
tmp.score += 1;
}
}
if (sCnt == 0) { // 맵에 산타가 없으면 즉시 종료
break;
}
}
// 점수 출력
Collections.sort(list);
for (int s = 1; s <= P; s++) {
Santa tmp = list.get(s);
sb.append(tmp.score + " ");
}
System.out.println(sb);
}
static void moving(int[] dir, int idx, int who) { // 부딪혀서 이동
int y = list.get(idx).y; // 시작 y
int x = list.get(idx).x; // 시작 x
if (who == 0) {
who = C; // 루돌프가 부딪혔을 경우
} else who = D;
if (!isRange(y + dir[0]*who, x+ dir[1]*who)) {
santaOut(idx); // 범위 벗어나면 탈락처리
return;
}
y += dir[0] * who;
x += dir[1] * who;
list.get(idx).y = y;
list.get(idx).x = x;
while (true) { // 밀려나기
if (map[y][x] != 0) { // 움직인 칸에 산타가 있을 경우
int nowIdx = map[y][x]; // 부딪힌 산타 idx
if (isRange(y+dir[0], x+dir[1])) {
list.get(nowIdx).y += dir[0];
list.get(nowIdx).x += dir[1];
y += dir[0];
x += dir[1];
} else {
santaOut(nowIdx); // 범위 밖이면 산타 탈락
return;
}
} else return;
}
}
static void moveSanta(int idx, int turn) {
int y = list.get(idx).y; // 기준 y
int x = list.get(idx).x; // 기준 x
int startDist = calDist(ry, rx, y, x); // 현재 산타 위치와 루돌프 간의 거리
int endY = y;
int endX = x;
int dist = startDist; // 움직이지 않았을 때(현재) 기준 거리로 초기화
int[][] dirs = {{-1,0}, {0,1}, {1,0}, {0,-1}}; // 상 우 하 좌 순서
int[] endDir = new int[2];
for (int[] dir : dirs) {
endY = y + dir[0];
endX = x + dir[1];
if (isRange(endY, endX) && (map[endY][endX] == 0 || map[endY][endX] == -1)) { // 범위 내에 있고 해당 칸에 아무도 없거나 루돌프면
int tmpDist = calDist(ry, rx, endY, endX);
if (tmpDist < dist) {
dist = tmpDist;
list.get(idx).y = endY;
list.get(idx).x = endX;
endDir[0] = dir[0];
endDir[1] = dir[1];
}
}
}
if (dist != startDist) { // 움직였을 경우
if (map[list.get(idx).y][list.get(idx).x] == -1) { // 도착한 칸에 루돌프가 있는 경우
list.get(idx).score += D;
list.get(idx).canMove = turn;
map[list.get(idx).y-endDir[0]][list.get(idx).x-endDir[1]] = 0;
moving(otherDir(endDir), idx, 1); // 반대 방향으로 밀려나기
}
}
}
static int[] otherDir (int[] dir) {
if (dir[0] == -1 && dir[1] == 0) return new int[]{1,0};
if (dir[0] == 0 && dir[1] == 1) return new int[]{0,-1};
if (dir[0] == 1 && dir[1] == 0) return new int[]{-1,0};
else return new int[]{0,1}; //(dir[0] == 0 && dir[1] == -1)
}
static void moveRudolf(int turn) {
int santaX = 0;
int santaY = 0;
int dist = 99999999;
for (int y = N; y >= 1; y--) { // y좌표 큰 산타부터
for (int x = N; x >= 1; x--) { //x좌표 큰 산타부터
if (map[y][x] == 0 || map[y][x] == -1) continue;
int tmpDist = calDist(ry, rx, y, x);
if (tmpDist < dist) { // 거리, y, x 업데이트
dist = tmpDist;
santaX = x;
santaY = y;
}
}
}
int[] go = whereToGoR(santaY, santaX); // 최종 산타 위치로 움직일 거리 찾기
ry += go[0]; // 루돌프 움직이기
rx += go[1];
if (map[ry][rx] != 0) { // 산타와 루돌프가 충돌 했을 경우
int sIdx = map[ry][rx]; // 충돌한 산타 인덱스
list.get(sIdx).score += C; // 점수 얻기
moving(go, sIdx, 0);
list.get(sIdx).canMove = turn; // 기절 상태로 변경
}
}
static void santaOut(int idx) { // 산타 탈락 처리
map[list.get(idx).y][list.get(idx).x] = 0;
list.get(idx).x = 0;
list.get(idx).y = 0; // 맵 밖으로 빼기
}
static int[] whereToGoR(int sy, int sx) { // 루돌프가 어느 방향으로 가야하는지 움직여야하는 y,x 거리 리턴
int[][] dirs = {{1,1}, {1,0}, {1,-1}, {0,1}, {0,-1}, {-1,1}, {-1,0}, {-1,-1}};
int dist = 99999999;
int[] go = new int[2];
for (int[] dir : dirs) {
int tmpDist = calDist(ry+dir[0], rx+dir[1], sy, sx);
if (tmpDist < dist) {
dist = tmpDist;
go[0] = dir[0]; // y
go[1] = dir[1]; // x
}
}
return go;
}
static int calDist(int y1, int x1, int y2, int x2) { // 산타와 루돌프 사이 거리 계산
return (y2-y1)*(y2-y1) + (x2-x1)*(x2-x1);
}
static boolean isRange(int y, int x) { // 맵 범위 안에 있는지 확인
return (y >= 1 && y <= N && x >= 1 && x <= N);
}
static void refreshMap() {
map = new int[N+1][N+1];
map[ry][rx] = -1; // 루돌프
for (int i = 1; i <= P; i++) {
Santa s = list.get(i);
if (isRange(s.y, s.x)) { // 범위 내에 있는 산타만 기록
map[s.y][s.x] = i;
}
}
}
static void printMap() {
for (int i = 1; i < N+1; i++) {
System.out.println();
for (int j = 1; j < N+1; j++) {
System.out.print(map[i][j] + " ");
}
}
System.out.println();
}
}
class Santa implements Comparable<Santa> {
int idx, y, x, score, canMove;
public Santa (int idx, int y, int x, int score, int canMove) {
this.idx = idx;
this.y = y;
this.x = x;
this.score = score;
this.canMove = canMove;
}
@Override
public int compareTo(Santa o) {
return this.idx - o.idx;
}
}'알고리즘' 카테고리의 다른 글
| [코드트리] 고대 문명 유적 탐사 (JAVA) (0) | 2024.12.05 |
|---|