[알고리즘] 싸움땅

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

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

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int m;
	static int k;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static PriorityQueue<Integer>[][] map;
	static int[][] player;
	static Point[] point;
	static int[] dir;
	static int[] ability;
	static int[] gun;
	static int[] score;
	public static void main(String[] args) 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());
		k = Integer.parseInt(st.nextToken());
		
		dir = new int[m+1];        
		ability = new int[m+1];    
		point = new Point[m+1];
		gun = new int[m+1];        
		score = new int[m+1];
		
		player = new int[n+1][n+1];
		map = new PriorityQueue[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				map[i][j] = new PriorityQueue<>(new Comparator<Integer>() {

					@Override
					public int compare(Integer o1, Integer o2) {
						// TODO Auto-generated method stub
						return Integer.compare(o2, o1);
					}
				});
				
				int gun = Integer.parseInt(st.nextToken());
				map[i][j].add(gun);
			}
		}
		
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			point[i] = new Point();
			point[i].x = Integer.parseInt(st.nextToken());
			point[i].y = Integer.parseInt(st.nextToken());
			dir[i] = Integer.parseInt(st.nextToken());
			ability[i] = Integer.parseInt(st.nextToken());
			
			player[point[i].x][point[i].y] = i;
		}
		
		for (int i = 1; i <= k; i++) {
			round();
		}
		
		for (int i = 1; i <= m; i++) {
			System.out.print(score[i] + " ");
		}
	}
	
	private static void print() {
		for (int i = 1; i <= m; i++) {
			System.out.println(i + " " + point[i]);
		}
	}
	
	private static void round() {
		// 한 칸만큼 이동을 한다. 만약 해당 방향으로 나갈 때 격자를 벗어나는 경우에는
		// 정반대 방향으로 방향을 바꾸어서 1만큼 이동한다.
		for (int i = 1; i <= m; i++) {
			
			move(i);
			
			
			// 2-1 만약 이동한 방향에 플레이어가 없다면 해당 칸에 총이 있는지 확인한다.
			// 플레이어가 총이 없으면 제일 큰 총을 획득하고 있으면 버리고 획득한다.
			if (player[point[i].x][point[i].y] == 0) {
				player[point[i].x][point[i].y] = i;
				findGun(i);
				continue;
			}
			// 2-2-1 만약 이동한 방향에 플레이어가 있다면 싸운다.
			// 해당 플레이어의 초기 능력치와 가지고 있는 총의 공격력의 합을 비교하여 더 큰 플레이어가 이긴다.
			// 같으면 초기 능력치가 높은 플레이어가 이긴다.
			// 이긴 플레이어는 초기 능력치와 가지고 있는 총의 공격력의 합의 차이만큼을 포인트로 획득한다.
			int opponent = player[point[i].x][point[i].y];
			
			int meAttk = ability[i] + gun[i];
			int opponentAttk = ability[opponent] + gun[opponent];
			
			int winner;
			int loser;
			if (meAttk == opponentAttk) {
				if (ability[i] > ability[opponent]) {
					winner = i;
					loser = opponent;
				} else {
					winner = opponent;
					loser = i;
				}
			} else {
				if (meAttk > opponentAttk) {
					winner = i;
					loser = opponent;
				} else {
					winner = opponent;
					loser = i;
				}
			}
			
			// 포인트 획득
			score[winner] += Math.abs(meAttk - opponentAttk);
			// winner는 원래 자리에 있는다.
			if (winner == i) {
				player[point[i].x][point[i].y] = i;
			}
			
			// 2-2-2 진 플레이어는 총을 해당 격자에 내려놓고, 
			// 해당 프레이어가 원래 가지고 있던 방향대로 한 칸 이동한다.
			// 만약 이동하려는 칸에 다른 플레이어가 있거나 격자 범위 밖인 경우에는 오른쪽으로 90도씩 회전하여
			// 빈칸이 보이는 순간 이동한다.
			// 만약 해당 칸에 총이 있다면, 해당 플레이어는 가장 공격력이 높은 총을 획득하고 나머지 총들은 격자에 내려 놓는다.
			
			// 총 내려놓기
			map[point[winner].x][point[winner].y].add(gun[loser]);
			gun[loser] = 0;
			
			// loser 이동
			for (int k = 0; k < 4; k++) {
				int nx = point[loser].x + dx[(dir[loser] + k) % 4];
				int ny = point[loser].y + dy[(dir[loser] + k) % 4];
				
				if (1 <= nx && nx <= n && 1 <= ny && ny <= n && player[nx][ny] == 0) {
					player[nx][ny] = loser;
					point[loser].x = nx;
					point[loser].y = ny;
					dir[loser] = (dir[loser] + k) % 4;
					break;
				}
			}
			findGun(loser);
			
			// 2-2-3 이긴 플레이어는 승리한 칸에 떨어져 있는 총들과 원래 들고 있던 총 중 가장 공격력이
			// 높은 총을 획득하고 나머지 총들은 해당 격자에 내려 놓는다.
			findGun(winner);
			
		}
		
		
	}

	private static void findGun(int i) {
		if (map[point[i].x][point[i].y].isEmpty()) {
			return;
		}
		int maxGun = map[point[i].x][point[i].y].peek();
		
		// 총이 없다면
		if (gun[i] == 0) {
			gun[i] = map[point[i].x][point[i].y].poll();
		} else {
			// 총이 있고 더 큰 총이 있다면 갱신
			if (gun[i] < maxGun) {
				int temp = gun[i];
				gun[i] =  map[point[i].x][point[i].y].poll();
				map[point[i].x][point[i].y].add(temp);
			}
		}
	}

	private static void move(int i) {
		
		// 이동
		player[point[i].x][point[i].y] = 0;
		
		int nx = point[i].x + dx[dir[i]];
		int ny = point[i].y + dy[dir[i]];
		
		if (!(1 <= nx && nx <= n && 1 <= ny && ny <= n)) {
			// 0 -> 2, 2 -> 0
			// 1 -> 3, 3 -> 1
			dir[i] = (dir[i] + 2) % 4;
			nx = point[i].x + dx[dir[i]];
			ny = point[i].y + dy[dir[i]];
		}
		
		point[i].x = nx;
		point[i].y = ny;
	}

}

나의 풀이

- 차근차근 따라가면 해주면 되는 문제