알고리즘/코드트리
루돌프의 반란[G2]
블랑v
2024. 4. 9. 00:14
문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
코드
/*
2120
==> 빠듯하게 3시간..
디버거 하나하나 다 찍고 검증
Break문과 return, Continue를 잘 검증하자..
*/
import java.io.*;
import java.util.*;
public class Main {
static int N,M,P,C,D;
static int[][] map;
static Santa rudolf;
static Santa[] santas;
static Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if(a[0] == b[0]) {
if(a[1] == b[1]) {
return -Integer.compare(a[2], b[2]);
}
return -Integer.compare(a[1], b[1]);
}
return Integer.compare(a[0], b[0]);
}
});
//우선순위 : URDL
static final int[] DR = {-1, 0, 1, 0};
static final int[] DC = {0, 1, 0, -1};
//8방향 이동
static final int[] ER = {-1, -1, -1, 0, 0, 1, 1, 1};
static final int[] EC = {-1, 0, 1, -1, 1, -1, 0, 1};
public static void main(String[] args) throws Exception {
input();
for(int i = 0; i < M; i++) {
moveRudolf(); //루돌프 이동
// debug(i);
moveSanta(); //산타 이동
// debug(i);
if(isEnded()) break; //모두 죽었는지 확인
checkEnd(); //턴 종료 요소들 확인
}
int answer = 0;
for(int i = 0; i < P; i++) {
System.out.print(santas[i].point + " ");
}
}
static void debug(int idx) {
System.out.println("=================" + idx);
System.out.println("루돌프 : " + rudolf.r + " " + rudolf.c);
for(int i = 0; i < P; i++) {
System.out.print(" [좌표] " + santas[i].r + ", " + santas[i].c);
if(santas[i].isEnd) System.out.print(" (탈락)");
System.out.println();
}
System.out.println("==================");
}
static void checkEnd() {
//턴 끝날때 점수 올리기, 스턴 -1
for(int i = 0; i < P; i++) {
if(santas[i].isEnd) continue;
santas[i].point += 1;
santas[i].isStun = Math.max(santas[i].isStun - 1, 0);
}
}
static boolean isEnded() {
for(int i = 0; i < P; i++) {
if(!santas[i].isEnd) return false;
}
return true;
}
static void moveSanta() {
for(int i = 0; i < P; i++) {
Santa nowSanta = santas[i];
if(nowSanta.isEnd || nowSanta.isStun > 0) continue; //탈락 및 기절
//루돌프와 가까워지는 방향 찾기
int beforeDist = calculate(nowSanta); //현재 거리
int wayResult = -1;
for(int d = 0; d < 4; d++) {
int nr = nowSanta.r + DR[d];
int nc = nowSanta.c + DC[d];
if(cantGo(nr, nc) || checkAnotherSanta(nr, nc)) continue; //맵밖이거나 다른 산타
int nowRes = calculate(nr, nc);
if(beforeDist > nowRes) {
beforeDist = nowRes;
wayResult = d;
}
}
//만약 줄어드는 거리가 없거나, 갈수가 없다면 그대로 유지
if(wayResult == -1) continue;
//아니라면 이동
nowSanta.r += DR[wayResult];
nowSanta.c += DC[wayResult];
//루돌프와 충돌했는지 확인
if(nowSanta.r == rudolf.r && nowSanta.c == rudolf.c) {
nowSanta.point += D; //점수 증가
nowSanta.r -= (DR[wayResult] * D); //반대로 D칸 밀려남
nowSanta.c -= (DC[wayResult] * D);
if(cantGo(nowSanta.r, nowSanta.c)) {
nowSanta.isEnd = true; //끝남
continue;
}
nowSanta.isStun = 2; //스턴
//여기 밀리는 다른 산타가 있나 확인
boolean[] check = new boolean[P];
check[i] = true; //ME
for(int j = 0; j < P; j++) {
if(check[j]) continue;
Santa nextSanta = santas[j]; //다른 산타
if(nextSanta.isEnd) continue; //탈락 스킵
if(nextSanta.r == nowSanta.r && nextSanta.c == nowSanta.c) {
chargedSanta(j, (wayResult + 2) % 4, check);
continue;
}
}
}
}
}
static void chargedSanta(int idx, int wayResult, boolean[] check) {
//이 산타 이동
Santa nowSanta = santas[idx];
nowSanta.r += DR[wayResult];
nowSanta.c += DC[wayResult];
check[idx] = true;
if(cantGo(nowSanta.r, nowSanta.c)) {
nowSanta.isEnd = true;
return;
}
//이동한 곳에 다른 산타가 있었는지
for(int i = 0; i < P; i++) {
if(check[i] || santas[i].isEnd) continue;
Santa nextSanta = santas[i];
if(nowSanta.r == nextSanta.r && nowSanta.c == nextSanta.c) {
check[i] = true;
chargedSanta(i, wayResult, check);
return;
}
}
}
static boolean checkAnotherSanta(int r, int c) {
for(int i = 0; i < P; i++) {
Santa now = santas[i];
if(now.isEnd) continue;
if(now.r == r && now.c == c) return true;
}
return false;
}
static void moveRudolf() {
//같은 거리의 산타 찾기
pq.clear();
for(int i = 0; i < P; i++) {
if(santas[i].isEnd) continue; //스킵
int dist = calculate(santas[i]);
pq.add(new int[] {dist, santas[i].r, santas[i].c, i});
}
Santa target = santas[pq.poll()[3]]; //타겟 인덱스
int beforeDist = calculate(target); //현재 거리
int wayResult = -1;
for(int i = 0; i < 8; i++) {
int nr = rudolf.r + ER[i];
int nc = rudolf.c + EC[i];
if(cantGo(nr, nc)) continue;
int nowRes = calculate(target, nr, nc);
if(beforeDist > nowRes) {
beforeDist = nowRes;
wayResult = i;
}
}
//이동 및 해당 위치에 산타 있는지 탐지
rudolf.r += ER[wayResult];
rudolf.c += EC[wayResult]; //이동
boolean check[] = new boolean[P];
for(int i = 0; i < P; i++) {
Santa now = santas[i];
if(rudolf.r == now.r && rudolf.c == now.c) {
charged(i, wayResult, check); //산타 밀림
}
}
}
static void charged(int idx, int wayResult, boolean[] check) {
Santa nowSanta = santas[idx];
check[idx] = true; //중첩 표시
nowSanta.point += C; //포인트 추가
nowSanta.isStun = 2; //스턴
//1. 산타 위치 이동 및 체크
int nr = nowSanta.r + (ER[wayResult] * C);
int nc = nowSanta.c + (EC[wayResult] * C);
nowSanta.r = nr; //이동 적용
nowSanta.c = nc;
if(cantGo(nr, nc)) {
nowSanta.isEnd = true; //탈락
return; //여긴 산타 x
}
//2. 이동한 위치에 다른 사람이 있다면 연계
for(int i = 0; i < P; i++) {
if(check[i]) continue;
Santa anotherSanta = santas[i];
if(anotherSanta.isEnd) continue; //탈락
if(nr == anotherSanta.r && nc == anotherSanta.c) { //연쇄작용
chargedOnePoint(i, wayResult, check); //한칸 밀고 다른 산타 있나 확인
return; //종료
}
}
}
static void chargedOnePoint(int idx, int wayResult, boolean[] check) {
Santa nowSanta = santas[idx];
check[idx] = true; //중첩 표시
//이 산타는 기절 X
int nr = nowSanta.r + ER[wayResult];
int nc = nowSanta.c + EC[wayResult];
nowSanta.r = nr; //이동 적용
nowSanta.c = nc;
if(cantGo(nr, nc)) {
nowSanta.isEnd = true; //탈락
return; //여긴 산타 x
}
//이 산타때문에 연쇄작용하는 다른 산타가 있는지 확인
for(int i = 0; i < P; i++) {
if(check[i]) continue;
Santa anotherSanta = santas[i];
if(anotherSanta.isEnd) continue; //탈락
if(nr == anotherSanta.r && nc == anotherSanta.c) { //연쇄작용
chargedOnePoint(i, wayResult, check); //한칸 밀고 다른 산타 있나 확인
return;
}
}
}
public static int calculate(Santa santa) {
return (int) (Math.pow(Math.abs(santa.r - rudolf.r), 2) + Math.pow(Math.abs(santa.c - rudolf.c), 2));
}
public static int calculate(Santa santa, int r, int c) {
return (int) (Math.pow(Math.abs(santa.r - r), 2) + Math.pow(Math.abs(santa.c - c), 2));
}
public static int calculate(int r, int c) {
return (int) (Math.pow(Math.abs(r - rudolf.r), 2) + Math.pow(Math.abs(c - rudolf.c), 2));
}
public static boolean cantGo(int r, int c) {
if(r < 0 || c < 0 || r >= N || c >=N) return true;
else return false;
}
public static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
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()); //산타 힘
st = new StringTokenizer(br.readLine());
rudolf = new Santa(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
santas = new Santa[P];
for(int i = 0; i < P; i++) {
st = new StringTokenizer(br.readLine());
int idx = Integer.parseInt(st.nextToken()) - 1;
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
santas[idx] = new Santa(r, c);
}
}
}
class Santa {
int r, c;
int point;
int isStun;
boolean isEnd;
public Santa(int r, int c) {
this.r = r;
this.c = c;
}
}