[Code Tree] 싸움땅(Java)
문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
풀이
[자료 구조]
- int[][] DELTAS: 사방 이동 좌표
- PriorityQueue<Integer>[][] guns: 격차에 위치한 총들의 공격력
- 내림차순 정렬
- int[][] players:
- 0번 인덱스: x 좌표
- 1번 인덱스: y 좌표
- 2번 인덱스: 방향
- 3번 인덱스: 초기 능력치
- 4번 인덱스: 총의 공격력
- int[][] map: 플레이어들의 위치
- int[] points: 플레이어들의 포인트
[풀이]
- k번 동안 1 ~ m번 플레이어들에 대해 순차적으로 아래 과정 반복한다.
1. 이동 방향으로 1칸 이동한다.
- 격자 밖으로 벗어나면 이동 방향의 정반대 방향((direction + 2) % 4)으로 1칸 이동
2. 플레이어가 이동한 곳이 비어있으면 플레이어의 총과 이동한 곳의 총들 중 가장 공격력이 높은 총을 챙기고, 나머지는 다시 내려놓는다.
3. 플레이어가 이동한 곳에 다른 플레이어가 있으면 싸움을 시작한다.
- 싸움의 승패는 플레이어의 '초기 능력치 + 총의 공격력'으로 결정한다.
- '초기 능력치 + 총의 공격력'이 큰 플레이어가 승자가 되고, '초기 능력치 + 총의 공격력'이 같으면 초기 능력치가 높은 플레이어가 승자가 된다.
- 싸움에서 진 플레이어는 총을 내려놓고, 원래 가던 방향으로 이동한다.
- 이동할 곳이 격자 밖이거나 다른 플레이어가 있으면 오른쪽으로 90도씩 회전하며 첫 번째로 찾은 빈 곳으로 이동한다.
- 이동한 곳에 총이 있으면 가장 공격력이 높은 총을 챙긴다.
- 싸움에서 이긴 플레이어는 플레이어의 총과 현재 위치에 있는 총들 중 가장 공격력이 높은 총을 챙기고, 나머지는 다시 내려놓는다.
- k번 반복이 끝나면 플레이어들의 포인트를 공백으로 구분해 출력한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
private static final int[][] DELTAS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private static final int EMPTY = 0;
private static final int X = 0;
private static final int Y = 1;
private static final int DIRECTION = 2;
private static final int INIT_ABILITY = 3;
private static final int GUN = 4;
private static PriorityQueue<Integer>[][] guns;
private static int[][] players;
private static int[][] map;
private static int n;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
n = Integer.parseInt(stringTokenizer.nextToken());
int m = Integer.parseInt(stringTokenizer.nextToken());
int k = Integer.parseInt(stringTokenizer.nextToken());
guns = new PriorityQueue[n][n];
for (int i = 0; i < n; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int j = 0; j < n; j++) {
int input = Integer.parseInt(stringTokenizer.nextToken());
guns[i][j] = new PriorityQueue<>(Comparator.reverseOrder());
if (input != EMPTY) {
guns[i][j].offer(input);
}
}
}
map = new int[n][n];
players = new int[m + 1][5];
for (int player = 1; player <= m; player++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int x = Integer.parseInt(stringTokenizer.nextToken()) - 1;
int y = Integer.parseInt(stringTokenizer.nextToken()) - 1;
int direction = Integer.parseInt(stringTokenizer.nextToken());
int initAbility = Integer.parseInt(stringTokenizer.nextToken());
players[player] = new int[]{x, y, direction, initAbility, EMPTY};
map[x][y] = player;
}
int[] points = new int[m + 1];
while (k-- > 0) {
for (int number = 1; number <= m; number++) {
int[] player = players[number];
map[player[X]][player[Y]] = EMPTY;
int dx = player[X] + DELTAS[player[DIRECTION]][X];
int dy = player[Y] + DELTAS[player[DIRECTION]][Y];
if (!isInRange(dx, dy)) {
dx -= DELTAS[player[DIRECTION]][X] * 2;
dy -= DELTAS[player[DIRECTION]][Y] * 2;
players[number][DIRECTION] = (player[DIRECTION] + 2) % 4;
}
if (map[dx][dy] == EMPTY) {
move(dx, dy, number);
selectPowerfulGun(number, player[GUN], dx, dy);
} else {
int enemy = map[dx][dy];
int winner = number;
int loser = enemy;
int player1 = player[INIT_ABILITY] + player[GUN];
int player2 = players[enemy][INIT_ABILITY] + players[enemy][GUN];
if (player1 < player2 || player1 == player2 && player[INIT_ABILITY] < players[enemy][INIT_ABILITY]) {
winner = enemy;
loser = number;
}
points[winner] += Math.abs(player1 - player2);
dropGun(dx, dy, loser);
moveLoser(dx, dy, loser);
move(dx, dy, winner);
selectPowerfulGun(winner, players[winner][GUN], dx, dy);
}
}
}
StringBuilder result = new StringBuilder();
for (int i = 1; i <= m; i++) {
result.append(points[i]).append(" ");
}
System.out.println(result);
}
private static boolean isInRange(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
private static void move(int dx, int dy, int number) {
map[dx][dy] = number;
players[number][X] = dx;
players[number][Y] = dy;
}
private static void selectPowerfulGun(int number, int gun, int x, int y) {
if (!guns[x][y].isEmpty() && guns[x][y].peek() > gun) {
players[number][GUN] = guns[x][y].poll();
if (gun != EMPTY) {
guns[x][y].offer(gun);
}
}
}
private static void moveLoser(int x, int y, int loser) {
for (int j = 0; j < 4; j++) {
int nextDirection = (players[loser][DIRECTION] + j) % 4;
int dx = x + DELTAS[nextDirection][X];
int dy = y + DELTAS[nextDirection][Y];
if (isInRange(dx, dy) && map[dx][dy] == EMPTY) {
move(dx, dy, loser);
players[loser][DIRECTION] = nextDirection;
if (!guns[dx][dy].isEmpty()) {
players[loser][GUN] = guns[dx][dy].poll();
}
return;
}
}
}
private static void dropGun(int x, int y, int loser) {
if (players[loser][GUN] != EMPTY) {
guns[x][y].offer(players[loser][GUN]);
players[loser][GUN] = EMPTY;
}
}
}