🔗 문제 링크
이 문제는 R×C 크기의 격자 위에서 진행됩니다.
격자에는 나의 로봇("I")과 상대 로봇들("R")이 배치되어 있으며,
주어진 이동 명령에 따라 나의 로봇이 이동할 때마다 상대 로봇들은
나의 로봇을 향해 그리디하게 한 칸씩 이동합니다. 🤖➡️
특히, 상대 로봇이 같은 칸에 여러 개 모이면 모두 제거되고,
만약 나의 로봇이 상대 로봇과 같은 칸으로 이동하면 게임 오버가 됩니다. ❌
문제의 목표는 이동 명령을 모두 수행한 후의 최종 격자 상태를 출력하거나,
중간에 나의 로봇이 잡혔을 경우 "kraj <순서>"
를 출력하는 것입니다.
StringBuilder
의 사용, HashMap
의 키 생성 및 파싱 등HashMap
연산에 따른 오버헤드가 제거되어,import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static int[] moveSeq;
private static char[][] map;
private static Queue<int[]> opponents = new ArrayDeque<>();
private static int mx, my;
private static int[][] dir = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
private static int answer = 0;
public static void main(String[] args) throws IOException {
setting();
if (!isGamePossible()) System.out.println("kraj " + answer);
else printMap();
}
private static void printMap() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
System.out.println();
}
private static boolean isGamePossible() {
for (int i = 0; i < moveSeq.length; i++) {
answer++;
if (!isMovePossible(moveSeq[i]) || !isOpponentsPossible()) {
return false;
}
}
return true;
}
private static boolean isOpponentsPossible() {
Map<String, Integer> nextPosition = new HashMap<>();
int size = opponents.size();
for (int i = 0; i < size; i++) {
int[] cur = opponents.poll();
int ox = cur[0];
int oy = cur[1];
int nextDir = -1;
int sum = Integer.MAX_VALUE;
for (int j = 0; j < dir.length; j++) {
int dx = ox + dir[j][0];
int dy = oy + dir[j][1];
if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
int distance = Math.abs(mx - dx) + Math.abs(my - dy);
// System.out.println(mx + " " + my + " | " + dx + " " + dy + " | " + distance + " " + j);
if (sum > distance) {
sum = distance;
nextDir = j;
}
}
// System.out.println();
int dx = ox + dir[nextDir][0];
int dy = oy + dir[nextDir][1];
// System.out.println(dx + " " + dy);
map[ox][oy] = '.';
if (dx == mx && dy == my) return false;
sb.append(dx).append(",").append(dy);
nextPosition.put(sb.toString(), nextPosition.getOrDefault(sb.toString(), 0) + 1);
sb.setLength(0);
}
// System.out.println("size : " + nextPosition.keySet().size());
for (String cur : nextPosition.keySet()) {
if (nextPosition.get(cur) == 1) {
String[] splits = cur.split(",");
int x = Integer.parseInt(splits[0]);
int y = Integer.parseInt(splits[1]);
// System.out.println(x + " " + y);
opponents.add(new int[]{x, y});
map[x][y] = 'R';
}
}
// printMap();
return true;
}
private static boolean isMovePossible(int num) {
int dx = mx + dir[num][0];
int dy = my + dir[num][1];
if (map[dx][dy] == 'R') return false;
map[mx][my] = '.';
map[dx][dy] = 'I';
mx = dx;
my = dy;
// printMap();
return true;
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
for (int i = 0; i < N; i++) {
String mapInput = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = mapInput.charAt(j);
if (map[i][j] == 'I') {
my = j;
mx = i;
} else if (map[i][j] == 'R') opponents.add(new int[]{i, j});
}
}
String moveInput = br.readLine();
moveSeq = new int[moveInput.length()];
for (int i = 0; i < moveSeq.length; i++) {
moveSeq[i] = (moveInput.charAt(i) - '0') - 1;
}
}
}
HashMap
, Queue
등을 사용하여 기능적으로는 문제를 해결했지만,int[][] map
)을 사용하여 격자 내 로봇 위치를 직접 관리하고,