문제
입력
n은 격자의 크기, m은 플레이어의 수, k는 라운드의 수를 의미합니다.
이후 n개의 줄에 걸쳐 격자에 있는 총의 정보가 주어집니다.
이후 m개의 줄에 걸쳐 플레이어들의 정보 x, y, d, s가 공백을 사이에 두고 주어집니다
출력
k 라운드 동안 게임을 진행하면서 각 플레이어들이 획득한 포인트를 공백을 사이에 두고 출력하세요.
풀이
제한조건
- 2 ≤ n ≤ 20
- 1 ≤ m ≤ min(n^2,30)
- 1 ≤ k ≤ 500
- 1 ≤ 총의 공격력 ≤ 100,000
- 1 ≤ s ≤ 100
- 1 ≤ x, y ≤ n
접근방법
시뮬레이션
22년도 하반기에 출제되었던 문제다.
전형적인 A형 스타일의 문제이다.
해야할것을 정리 후, 차근차근 접근해보자.
크게 2가지의 기능을 구현해야 한다.
1. 이동
2. 결투1. 이동
플레이어가 이동하는 기능을 구현해야한다.
이동은 다시 2가지의 경우로 나뉜다.
- 각자의 차례에 이동
- 결투의 결과에 따라 이동
각각의 경우에 따라 방향 전환(우측, 뒤)을 생각하여 기능을 작성하자.
이동하기전, 이동할 칸에 대하여 아래와 같이 확인을 하게 된다면, 구현 과정에서 덜 헷갈리게 구현할 수 있다.
final static int OUT_OF_RANGE = 0;
final static int EXIST_PLAYER = 1;
final static int SAFE_AREA = 2;
private static int canGo(int n) {
int nx = players[n].x + dx[players[n].dir];
int ny = players[n].y + dy[players[n].dir];
// 범위 밖, 방향전환 필요
if (!isInRange(nx, ny))
return OUT_OF_RANGE;
// 해당 칸에 다른 사람이 있는 경우.
if (arr[nx][ny] >= 0)
return EXIST_PLAYER;
// 해당 칸은 안전함.
return SAFE_AREA;
}방향 전환의 경우 시계방향으로 문제에서 주어졌기 때문에 간단하게 구현할 수 있다.
void turnBack() {
dir = (dir + 2) % 4;
}
void turnRight() {
dir = (dir + 1) % 4;
}2. 결투
2차원 배열을 통해 각 플레이어가 어느 위치에 서있는지 추가적으로 확인해주자.
특정 플레이어의 차례에 이동을 했다면, 좌표정보를 이용해서 해당 지역에 다른 플레이어가 있었는지 확인할 수 있다.
이제 경우에 따라서 개별 구현을 해주면 된다.
int base = arr[x][y];
if (base != -1) {
// 누군가 있는 경우
// 결투
int winner = getWinner(i, base);
int awards = Math.abs(
(players[i].ability + players[i].gun) - (players[base].ability + players[base].gun));
if (winner == i) { // 이동한 플레이어 승
result(i, base);
score[i] += awards;
} else { // 원래 있던 플레이어 승
result(base, i);
score[base] += awards;
}
} else {
arr[x][y] = i;
if (!pq[x][y].isEmpty()) {
if (players[i].gun != 0)
pq[x][y].add(players[i].gun);
players[i].gun = pq[x][y].poll();
}
}3. 총 정리
각각의 좌표에 해당하는 우선순위 큐를 생성하여 관리하자.
각 플레이어는 이동 또는 결투 승리 시 해당 칸에 존재하는 공격력이 가장 높은 총을 습득한다.
따라서 우선순위 큐를 사용하여 해당칸의 가장 앞의 원소와 공격력을 비교하며 가장 높은 총을 꺼내서 본인이 가지고, 나머지는 큐에 다시 넣어준다.
- 내가 총이 없는 경우.
- 해당 위치에 총이 없는 경우.
위 2가지에 대한 예외처리를 해주자.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
static int N, M, K;
static StringBuilder sb = new StringBuilder();
static int[][] arr;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[] score;
static PriorityQueue<Integer>[][] pq;
static class Player {
int x;
int y;
int ability;
int gun;
int dir;
Player(String[] str) {
x = stoi(str[0]) - 1;
y = stoi(str[1]) - 1;
dir = stoi(str[2]);
ability = stoi(str[3]);
gun = 0;
}
void turnBack() {
dir = (dir + 2) % 4;
}
void turnRight() {
dir = (dir + 1) % 4;
}
void move() {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (isInRange(nx, ny)) {
x = nx;
y = ny;
} else {
turnBack();
move();
}
}
}
static Player[] players;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = in.readLine().split(" ");
N = stoi(inputs[0]);
M = stoi(inputs[1]);
K = stoi(inputs[2]);
arr = new int[N][N];
players = new Player[M];
score = new int[M];
pq = new PriorityQueue[N][N];
for (int i = 0; i < N; ++i) {
inputs = in.readLine().split(" ");
for (int j = 0; j < N; ++j) {
pq[i][j] = new PriorityQueue(Collections.reverseOrder());
arr[i][j] = -1;
int value = stoi(inputs[j]);
if (value != 0)
pq[i][j].add(stoi(inputs[j]));
}
}
for (int i = 0; i < M; ++i) {
inputs = in.readLine().split(" ");
players[i] = new Player(inputs);
arr[players[i].x][players[i].y] = i;
}
for (int t = 0; t < K; ++t)
simulation();
for (int i : score)
sb.append(i).append(" ");
System.out.println(sb);
}
private static void simulation() {
for (int i = 0; i < M; ++i) {
// i번 플레이어 이동.
if (canGo(i) == OUT_OF_RANGE)
players[i].turnBack();
int px = players[i].x;
int py = players[i].y;
arr[px][py] = -1;
players[i].move();
int x = players[i].x;
int y = players[i].y;
// 겹침 확인
int base = arr[x][y];
if (base != -1) {
// 누군가 있는 경우
// 결투
int winner = getWinner(i, base);
int awards = Math.abs(
(players[i].ability + players[i].gun) - (players[base].ability + players[base].gun));
if (winner == i) { // 이동한 플레이어 승
result(i, base);
score[i] += awards;
} else { // 원래 있던 플레이어 승
result(base, i);
score[base] += awards;
}
} else {
arr[x][y] = i;
if (!pq[x][y].isEmpty()) {
if (players[i].gun != 0)
pq[x][y].add(players[i].gun);
players[i].gun = pq[x][y].poll();
}
}
}
}
private static void result(int winner, int loser) {
int x = players[winner].x;
int y = players[winner].y;
if (players[loser].gun != 0) {
pq[x][y].add(players[loser].gun);
players[loser].gun = 0;
}
if (players[winner].gun != 0) {
pq[x][y].add(players[winner].gun);
players[winner].gun = 0;
}
if (!pq[x][y].isEmpty())
players[winner].gun = pq[x][y].poll();
arr[x][y] = winner;
for (int d = 0; d < 4; ++d) {
if (canGo(loser) == SAFE_AREA) {
players[loser].move();
arr[players[loser].x][players[loser].y] = loser;
if (!pq[players[loser].x][players[loser].y].isEmpty())
players[loser].gun = pq[players[loser].x][players[loser].y].poll();
break;
}
players[loser].turnRight();
}
}
private static int getWinner(int p1, int p2) {
if (players[p1].ability + players[p1].gun == players[p2].ability + players[p2].gun) {
if (players[p1].ability > players[p2].ability)
return p1;
return p2;
}
if (players[p1].ability + players[p1].gun > players[p2].ability + players[p2].gun)
return p1;
return p2;
}
final static int OUT_OF_RANGE = 0;
final static int EXIST_PLAYER = 1;
final static int SAFE_AREA = 2;
private static int canGo(int n) {
int nx = players[n].x + dx[players[n].dir];
int ny = players[n].y + dy[players[n].dir];
// 범위 밖, 방향전환 필요
if (!isInRange(nx, ny))
return OUT_OF_RANGE;
// 해당 칸에 다른 사람이 있는 경우.
if (arr[nx][ny] >= 0)
return EXIST_PLAYER;
// 해당 칸은 안전함.
return SAFE_AREA;
}
private static boolean isInRange(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < N)
return true;
return false;
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}