알고리즘 풀이/Java
[알고리즘][X] 메이즈 러너
Dong's Universe
2024. 3. 30. 02:03
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int K;
static int[] exit;
static int[][] info;
static int move = 0;
static List<int[]> rotatePerson = new ArrayList<>();
static int[][] people;
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());
info = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
info[i][j] = Integer.parseInt(st.nextToken());
}
}
// r, c, isExit 1: exit, 0: not exit
people = new int[M][3];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 2; j++) {
people[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
// exit 좌표 구하기
exit = new int[2];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 2; i++) {
exit[i] = Integer.parseInt(st.nextToken()) - 1;
}
for (int k = 0; k < K; k++) {
// System.out.println("before");
// for (int[] person : people) {
// if (person[2] == 1) {
// continue;
// }
// System.out.println(person[0] + " " + person[1]);
// }
// System.out.println();
// 1. 움직인다.
for (int i = 0; i < M; i++) {
if (people[i][2] == 1) {
continue;
}
move(people[i], info);
}
// 2. 미로가 회전한다.
rotate(people);
// System.out.println("after");
// for (int[] person : people) {
// if (person[2] == 1) {
// continue;
// }
// System.out.println(person[0] + " " + person[1]);
// }
// System.out.println();
}
System.out.println(move);
System.out.println((exit[0]+1) + " " + (exit[1]+1));
//debug
// for (int[] person : people) {
// if (person[2] == 1) {
// continue;
// }
// move(person, info);
// }
// System.out.println(Arrays.deepToString(people));
// int[][] temp = new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//
// System.out.println(Arrays.deepToString(realRotate(temp)));
// int[] square = findSquare(people);
// System.out.println(Arrays.toString(square));
// execute(square[0], square[1], square[2]);
// System.out.println(Arrays.deepToString(people));
}
// 동시에 움직임, 사람 이미 나갔을 수 있음
private static void move(int[] person, int[][] info) {
int x = person[0];
int y = person[1];
int e = person[2];
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int minDist = Math.abs(x - exit[0]) + Math.abs(y - exit[1]);
int rnx = -1;
int rny = -1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!(0 <= nx && nx < N && 0 <= ny && ny < N && info[nx][ny] == 0)) {
continue;
}
int dist = Math.abs(nx - exit[0]) + Math.abs(ny - exit[1]);
if (dist < minDist) {
minDist = dist;
rnx = nx;
rny = ny;
break;
}
}
if (rnx == -1 && rny == -1) { // 못 움직임
return;
} else { // 움직임
move++;
if (rnx == exit[0] && rny == exit[1]) {
person[2] = 1;
return;
}
person[0] = rnx;
person[1] = rny;
}
}
private static void rotate(int[][] people) {
rotatePerson = new ArrayList<>();
int[] square = findSquare(people);
if (square == null) {
return;
}
execute(square[0], square[1], square[2]);
}
private static void execute(int r, int c, int size) {
int[][] temp = new int[size][size];
for (int i = r; i < r + size; i++) {
for (int j = c; j < c + size; j++) {
if (i == exit[0] && j == exit[1]) {
temp[i - r][j - c] = -1;
continue;
}
temp[i - r][j - c] = info[i][j];
}
}
List<Integer>[][] list = new List[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
list[i][j] = new ArrayList<>();
}
}
// System.out.println("size = " + size);
for (int[] person : rotatePerson) {
int i = person[0];
int j = person[1];
// System.out.println("rotate " + i + " " + j);
// temp[i - r][j - c] = -person[2] - 10;
list[j][size-1-i].add(person[2]);
}
// [i][j] -> [j][size-1-i]
temp = realRotate(temp);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (temp[i][j] > 0) {
temp[i][j]--;
}
}
}
for (int i = r; i < r + size; i++) {
for (int j = c; j < c + size; j++) {
if (temp[i - r][j - c] == -1) {
// System.out.println("test " + i + " " + j);
info[i][j] = 0;
exit[0] = i;
exit[1] = j;
} else if (!list[i - r][j - c].isEmpty()) {
info[i][j] = 0;
// int idx = -temp[i - r][j - c] - 10;
for (int idx : list[i-r][j-c]) {
// System.out.println(i + " " + j);
people[idx][0] = i;
people[idx][1] = j;
}
} else {
info[i][j] = temp[i - r][j - c];
}
}
}
}
private static int[][] realRotate(int[][] temp) {
int size = temp.length;
int[][] rotate = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
rotate[j][size-1-i] = temp[i][j];
}
}
return rotate;
}
// 정사각형 좌상단 포인트 r, c, size
private static int[] findSquare(int[][] people) {
for (int size = 1; size < N; size++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int ex = exit[0];
int ey = exit[1];
if (!(i <= ex && ex <= i + size && j <= ey && ey <= j + size)) {
continue;
}
boolean flag = false;
for (int k = 0; k < people.length; k++) {
int[] person = people[k];
if (person[2] == 1) {
continue;
}
int px = person[0];
int py = person[1];
if (i <= px && px <= i + size && j <= py && py <= j + size) {
// System.out.println(px + " " + py + " " + k);
rotatePerson.add(new int[] {px - i, py - j, k});
flag = true;
}
}
if (flag) {
return new int[] {i, j, size+1};
}
}
}
}
return null;
}
}나의 풀이
- 하나의 칸에 여러 사람이 들어갈 수 있는 조건을 놓쳐서 틀렸고 디버깅이 어려웠다.
- 문제에 있는 말들은 그 어떤 것도 의미 없는 게 없다. 따라서 사소한 거라도 중요하게 보자!!