충돌 시뮬레이션
매 턴마다 살아있는 산타에게 점수 부여, 루돌프랑 부딪힌 산타 점수 부여
이러한 방식으로 모든 턴 or 모든 산타가 리타이어될 때까지 수행 후 점수 합산.
문제 설명
1번부터 P번까지 P 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!
게임판 구성
- 게임판은 N×N 크기의 격자로 이루어져 있습니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
- 게임은 총 M 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 P번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.
- 게임판에서 두 칸 사이의 거리는 로 계산됩니다.
루돌프의 움직임
- 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다. 단, 게임에서 탈락하지 않은 산타 중 가장 가까운 산타를 선택해야 합니다.
- 만약 가장 가까운 산타가 2명 이상이라면, r 좌표가 큰 산타를 향해 돌진합니다. r이 동일한 경우, c 좌표가 큰 산타를 향해 돌진합니다.
- 루돌프는 상하좌우, 대각선을 포함한 인접한 8방향 중 하나로 돌진할 수 있습니다. (편의상 인접한 대각선 방향으로 전진하는 것도 1칸 전진하는 것이라 생각합니다.) 가장 우선순위가 높은 산타를 향해 8방향 중 가장 가까워지는 방향으로 한 칸 돌진합니다.
산타의 움직임
- 산타는 1번부터 P번까지 순서대로 움직입니다.
- 기절했거나 이미 게임에서 탈락한 산타는 움직일 수 없습니다.
- 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.
- 산타는 다른 산타가 있는 칸이나 게임판 밖으로는 움직일 수 없습니다.
- 움직일 수 있는 칸이 없다면 산타는 움직이지 않습니다.
- 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타는 움직이지 않습니다.
- 산타는 상하좌우로 인접한 4방향 중 한 곳으로 움직일 수 있습니다. 이때 가장 가까워질 수 있는 방향이 여러 개라면, 상우하좌 우선순위에 맞춰 움직입니다.
충돌
- 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다.
- 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 C만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해온 방향으로 C 칸 만큼 밀려나게 됩니다.
- 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 D만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해온 반대 방향으로 D 칸 만큼 밀려나게 됩니다.
- 밀려나는 것은 포물선 모양을 그리며 밀려나는 것이기 때문에 이동하는 도중에 충돌이 일어나지는 않고 정확히 원하는 위치에 도달하게 됩니다.
- 만약 밀려난 위치가 게임판 밖이라면 산타는 게임에서 탈락됩니다.
- 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용이 발생합니다.
상호작용
- 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다.
- 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다. 그 옆에 산타가 있다면 연쇄적으로 1칸씩 밀려나는 것을 반복하게 됩니다. 게임판 밖으로 밀려나오게 된 산타의 경우 게임에서 탈락됩니다.
기절
- 산타는 루돌프와의 충돌 후 기절을 하게 됩니다. 현재가 k번째 턴이었다면, (k+1)번째 턴까지 기절하게 되어 (k+2)번째 턴부터 다시 정상상태가 됩니다.
- 기절한 산타는 움직일 수 없게 됩니다. 단, 기절한 도중 충돌이나 상호작용으로 인해 밀려날 수는 있습니다.
- 루돌프는 기절한 산타를 돌진 대상으로 선택할 수 있습니다.
게임 종료
- M 번의 턴에 걸쳐 루돌프, 산타가 순서대로 움직인 이후 게임이 종료됩니다.
- 만약 P 명의 산타가 모두 게임에서 탈락하게 된다면 그 즉시 게임이 종료됩니다.
- 매 턴 이후 아직 탈락하지 않은 산타들에게는 1점씩을 추가로 부여합니다.
- 각 산타가 얻은 최종 점수를 구하는 프로그램을 작성
입력 형식
첫 번째 줄에 가 공백을 사이에 두고 주어집니다.
다음 줄에는 루돌프의 초기 위치 가 주어집니다.
다음 개의 줄에 걸쳐서 산타의 번호 과 초기 위치 가 공백을 사이에 두고 주어집니다.
처음 산타와 루돌프의 위치는 겹쳐져 주어지지 않음을 가정해도 좋습니다.
- : 게임판의 크기
- : 게임 턴 수
- : 산타의 수
- : 루돌프의 힘
- : 산타의 힘
- : 산타의 번호
- : 루돌프의 초기 위치
- : 산타의 초기 위치
출력 형식
게임이 끝났을 때 각 산타가 얻은 최종 점수를 1번부터 번까지 순서대로 공백을 사이에 두고 출력합니다.
문제 풀이
루돌프의 움직임 : moveToSanta()
static void moveToSanta(Santa[] santas, Santa target, Rudolf rudolf) {
int row = 0; // 최소 거리가 되는 row
int col= 0; // 최소 거리가 되는 col
double dist = Double.MAX_VALUE; // 최소 거리
for(int i = 0; i < 8; i++) {
int dr = rudolf.row + rows[i]; // 현재 루돌프 위치에서 한 칸 이동할 때 row
int dc = rudolf.col + cols[i]; // 현재 루돌프 위치에서 한 칸 이동할 때 col
if(!isInRange(dr, dc)) continue; // 장외면 패스
if(dr == target.row && dc == target.col) { // 산타랑 부딪히면
bump(santas, target, i, dr, dc, 2, c); // 충돌 메서드 실행
row = dr;
col = dc;
break;
}
// 이동 할 수 있다면
double dd = Math.pow(target.row - dr, 2) +
Math.pow(target.col - dc, 2);
// 가까워지는 지 확인
if(dist <= dd) continue;
dist = dd;
row = dr;
col = dc;
}
map[row][col] = -1;
map[rudolf.row][rudolf.col] = 0;
rudolf.row = row;
rudolf.col = col;
}루돌프가 움직일 차례가 되었을 때, 루돌프가 움직일 수 있는 8방을 모두 확인함.
확인하는 요소는
1. 맵 안에서 움직이는지
2. 산타랑 부딪히는지
3. 산타랑 까워지는지
를 확인하면서 요구사항에 맞는 로직을 작성하면 된다.
산타의 움직임 : moveToRudolf()
static void moveToRudolf(Santa[] santas, Rudolf rudolf) {
for(int i = 1; i < p + 1; i++) { // 모든 산타를 돌면서
Santa santa = santas[i];
if(retire[santa.no]) continue; // 장외면 패스
if(santa.isStun > 0) { // 스턴 상태면
santa.isStun--; // 풀어주고
continue; // 패스
}
int row = santa.row; // 이동 전 row 저장
int col = santa.col; // 이동 후 col 저장
double dist = Math.pow(row - rudolf.row, 2) +
Math.pow(col - rudolf.col, 2); // 이동 전 루돌프까지의 거리 및 최소 거리
for(int j = 0; j < 4; j++) { // 상우하좌 순
int dr = row + rows[j]; // 이동 할 row
int dc = col + cols[j]; // 이동 할 col
if(!isInRange(dr, dc)) continue;
if(map[dr][dc] > 0) continue;
if(map[dr][dc] == -1) { // 루돌프랑 부딪히면
bump(santas, santa, (j + 2) % 4, dr, dc, 1, d); // 부딪히는 함수
break; // 주변 탐색 안해도 됨.
}
// 이동 할 위치와 루돌프 사이의 거리
double dd = Math.pow(dr - rudolf.row, 2) +
Math.pow(dc - rudolf.col, 2);
if(dist <= dd) continue; // 멀어지거나 이전 최소 거리와 같으면 패스
dist = dd; // 최소 거리 갱신
santa.row = dr; // 이동 할 row 갱신
santa.col = dc; // 이동 할 col 갱신
}
map[row][col] = 0; // 이전 히스토리 삭제
if(retire[santa.no]) continue;
map[santa.row][santa.col] = santa.no; // 산타 이동
}
}산타가 순서대로 이동해야함.
나머지는 주석 참조.
충돌 : bump()
static void bump(Santa[] santas, Santa santa, int dir, int row, int col, int stun, int push) {
map[santa.row][santa.col] = 0; // 충돌 전 위치 초기화
row += rows[dir] * push; // 점수만큼 밀려남.
col += cols[dir] * push;
scores[santa.no] += push; // 점수 합산
if(!isInRange(row, col)) { // 장외면
retire[santa.no] = true; // 리타이어 시키고
return; // 리턴. (굳이 리타이어된 산타의 위치를 갱신 시킬 필요 없음)
}
updateSantaPosition(santas, santa, row, col, dir); // 충돌되어 밀려난 산타의 위치 갱신
updateMap(santas); // 갱신된 위치로 맵 갱신
// 타겟 산타의 위치 및 상태 갱신
map[row][col] = santa.no;
santa.row = row;
santa.col = col;
santa.isStun = stun; // 기절
}실제로 산타가 이동한 뒤에 충돌을 확인하는 것이 아닌, 이동할 위치와 비교함.
즉, 산타가 이동할 위치에 루돌프가 있으면 그 위치로부터 밀려날 좌표를 계산.
updateSantaPosition()는 충돌로 인해 밀려난 산타 위치를 갱신시킴.
그리고 연쇄적으로 밀려나는 로직도 구현.
상호작용 : updateSantaPosition()
static void updateSantaPosition(Santa[] santas, Santa target, int row, int col, int dir) {
int nr = row;
int nc = col;
// 밀려날 위치에 다른 산타가 없거나 장외일 때까지 연쇄 충돌
while(true) {
if(map[nr][nc] == 0) break;
int no = map[nr][nc];
Santa s = santas[no];
s.row += rows[dir];
s.col += cols[dir];
nr = s.row;
nc = s.col;
if(!isInRange(nr, nc)) {
retire[s.no] = true;
break;
}
}
}전체 코드
코드 겁나 김...주의...
import java.io.*;
import java.util.*;
public class 루돌프의반란 {
static int n; // 게임판 크기
static int m; // 게임 턴 수
static int p; // 산타의 수
static int c; // 루돌프의 힘
static int d; // 산타의 힘
static int[][] map;
static int[] rows = {-1, 0, 1, 0, -1, -1, 1, 1};
static int[] cols = {0, 1, 0, -1, -1, 1, 1, -1};
static int[] scores;
static boolean[] retire;
static class Rudolf{
int row;
int col;
public Rudolf(int row, int col) {
this.row = row;
this.col = col;
}
}
static class Santa{
int no;
int row;
int col;
int isStun = 0;
public Santa(int no, int row, int col) {
this.no = no;
this.row = row;
this.col = col;
}
@Override
public String toString() {
return no + " " + row + " " + col + " " + isStun;
}
}
public static void main(String[] args) throws Exception{
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][n];
st = new StringTokenizer(br.readLine());
Rudolf rudolf = new Rudolf(Integer.parseInt(st.nextToken()) - 1,
Integer.parseInt(st.nextToken()) - 1);
map[rudolf.row][rudolf.col] = -1;
Santa[] santas = new Santa[p + 1];
for(int i = 0; i < p; i++) {
st = new StringTokenizer(br.readLine());
int no = Integer.parseInt(st.nextToken());
santas[no] = new Santa(no,
Integer.parseInt(st.nextToken()) - 1,
Integer.parseInt(st.nextToken()) - 1);
map[santas[no].row][santas[no].col] = no;
}
retire = new boolean[p + 1];
scores = new int[p + 1];
play(santas, rudolf);
for(int i = 1; i < p + 1; i++) sb.append(scores[i] + " ");
System.out.println(sb);
}
static void play(Santa[] santas, Rudolf rudolf) {
for(int round = 0; round < m; round++) {
// 가장 가까이 있는 산타 정하기
Santa target = getNearSanta(santas, rudolf);
// 없으면 나가기
if(target == null) return;
// 루돌프 : 가장 가까운 산타쪽으로 이동
moveToSanta(santas, target, rudolf);
// 산타 : 루돌프쪽으로 이동
moveToRudolf(santas, rudolf);
// 루돌프와 산타가 이동을 마치면
// 살아 남은 산타에게 점수 1점 추가
getPoint();
}
}
static void getPoint() {
for(int i = 1; i < p + 1; i++) {
if(retire[i]) continue;
scores[i]++;
}
}
static Santa getNearSanta(Santa[] santas, Rudolf rudolf) {
int dist = Integer.MAX_VALUE;
Santa target = null;
for(int i = 1; i < p + 1; i++) {
if(retire[i]) continue;
Santa santa = santas[i];
int d = (int) (Math.pow(santa.row - rudolf.row, 2) +
Math.pow(santa.col - rudolf.col, 2));
if(dist < d) continue;
if(dist == d) {
if(target.row > santa.row) continue;
if(target.row < santa.row) {
target = santa;
continue;
}
if(target.col > santa.col) continue;
target = santa;
}
target = santa;
dist = d;
}
return target;
}
static void moveToSanta(Santa[] santas, Santa target, Rudolf rudolf) {
int row = 0; // 최소 거리가 되는 row
int col= 0; // 최소 거리가 되는 col
double dist = Double.MAX_VALUE; // 최소 거리
for(int i = 0; i < 8; i++) {
int dr = rudolf.row + rows[i]; // 현재 루돌프 위치에서 한 칸 이동할 때 row
int dc = rudolf.col + cols[i]; // 현재 루돌프 위치에서 한 칸 이동할 때 col
if(!isInRange(dr, dc)) continue; // 장외면 패스
if(dr == target.row && dc == target.col) { // 산타랑 부딪히면
bump(santas, target, i, dr, dc, 2, c); // 충돌 메서드 실행
row = dr;
col = dc;
break;
}
double dd = Math.pow(target.row - dr, 2) +
Math.pow(target.col - dc, 2);
if(dist <= dd) continue;
dist = dd;
row = dr;
col = dc;
}
map[row][col] = -1;
map[rudolf.row][rudolf.col] = 0;
rudolf.row = row;
rudolf.col = col;
}
static void moveToRudolf(Santa[] santas, Rudolf rudolf) {
for(int i = 1; i < p + 1; i++) { // 모든 산타를 돌면서
Santa santa = santas[i];
if(retire[santa.no]) continue; // 장외면 패스
if(santa.isStun > 0) { // 스턴 상태면
santa.isStun--; // 풀어주고
continue; // 패스
}
int row = santa.row; // 이동 전 row 저장
int col = santa.col; // 이동 후 col 저장
double dist = Math.pow(row - rudolf.row, 2) +
Math.pow(col - rudolf.col, 2); // 이동 전 루돌프까지의 거리 및 최소 거리
for(int j = 0; j < 4; j++) { // 상우하좌 순
int dr = row + rows[j]; // 이동 할 row
int dc = col + cols[j]; // 이동 할 col
if(!isInRange(dr, dc)) continue;
if(map[dr][dc] > 0) continue;
if(map[dr][dc] == -1) { // 루돌프랑 부딪히면
bump(santas, santa, (j + 2) % 4, dr, dc, 1, d); // 부딪히는 함수
break; // 주변 탐색 안해도 됨.
}
// 이동 할 위치와 루돌프 사이의 거리
double dd = Math.pow(dr - rudolf.row, 2) +
Math.pow(dc - rudolf.col, 2);
if(dist <= dd) continue; // 멀어지거나 이전 최소 거리와 같으면 패스
dist = dd; // 최소 거리 갱신
santa.row = dr; // 이동 할 row 갱신
santa.col = dc; // 이동 할 col 갱신
}
map[row][col] = 0; // 이전 히스토리 삭제
if(retire[santa.no]) continue;
map[santa.row][santa.col] = santa.no; // 산타 이동
}
}
static boolean isInRange(int dr, int dc) {
if(dr >= 0 && dr < n && dc >= 0 && dc < n) return true;
return false;
}
static void bump(Santa[] santas, Santa santa, int dir, int row, int col, int stun, int push) {
map[santa.row][santa.col] = 0;
row += rows[dir] * push;
col += cols[dir] * push;
scores[santa.no] += push;
if(!isInRange(row, col)) {
retire[santa.no] = true;
return;
}
updateSantaPosition(santas, santa, row, col, dir);
updateMap(santas);
// 타겟 산타의 위치 및 상태 갱신
map[row][col] = santa.no;
santa.row = row;
santa.col = col;
santa.isStun = stun;
}
static void updateMap(Santa[] santas) {
for(Santa sa : santas) {
if(sa == null) continue;
if(retire[sa.no]) continue;
map[sa.row][sa.col] = sa.no;
}
}
static void updateSantaPosition(Santa[] santas, Santa target, int row, int col, int dir) {
int nr = row;
int nc = col;
// 밀려날 위치에 다른 산타가 없거나 장외일 때까지 연쇄 충돌
while(true) {
if(map[nr][nc] == 0) break;
int no = map[nr][nc];
Santa s = santas[no];
s.row += rows[dir];
s.col += cols[dir];
nr = s.row;
nc = s.col;
if(!isInRange(nr, nc)) {
retire[s.no] = true;
break;
}
}
}
}
한 걸음씩 꾸준히