루돌프의 반란[G2]

문제

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

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

 

코드

/*
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;
	}
}