문제

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

---

입력

첫 번째 줄에 N, M, K가 공백을 사이에 두고 주어집니다.
다음 N개의 줄에 걸쳐서 N×N 크기의 미로에 대한 정보가 주어집니다.
다음 줄에 출구의 좌표가 주어집니다. 출구는 빈 칸에만 주어집니다.

---

출력

게임 시작 후 K초가 지났거나, 모든 참가자가 미로를 탈출했을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력합니다.

---

풀이

제한조건

• N: 미로의 크기 (4≤N≤10)
• M: 참가자 수 (1≤M≤10)
• K: 게임 시간 (1≤K≤100)

접근방법

시뮬레이션

시간이 넉넉하다. 적당히만 방향을 잡아도 무리없이 통과할 수 있는 시간이다.

1. 참가자의 이동
2. 미로 회전
	- 정사각형 찾기
    - 회전시키기
    - 회전한 부분의 벽 내구도 감소

1. 참가자의 이동
참가자는 같은 좌표 상에 여러명이 도달할 수 있다.
따라서 특정 위치에 몇 번 플레이어가 있는지 확인하기 위하여 비트마스킹으로 표현해 두었다.

각 플레이어는 비트마스킹 표현을 통해 찾은 index로 바로 접근가능하게 만들어 두었다.

플레이어의 이동은 주변 4방향 중 이동가능하며, 현재위치보다 이동 시 더 가까운 거리가 되어야 한다.

별다른 어려운 구현항목이 없다.

2. 미로회전

• 정사각형 찾기
  처음에는 플레이어의 위치와 출구가 사각형의 모서리에 위치한다고 생각했다.
  하지만, 사각형 내부에 포함만 되면 된다. 모서리일 필요가 없다.

따라서 우선순위 조건에 따라

• 가장 변의 길이가 짧으며
• 가장 위쪽 라인이며
• 가장 왼쪽에 위치한
  사각형을 모두 순회하며 가장 먼저 조건을 만족하는 사각형을 찾았다.

해당 사각형을 시계방향으로 90도 회전하고 종료한다.

배열의 회전은 백준의 '배열돌리기'와 같은 문제를 풀면 연습할 수 있다.

또한 회전되는 영역중 벽이 있는 위치는 내구도를 감소시켜주자.

문제를 풀면서 알고리즘 적으로 어려운것을 요구하지 않는다.
또한 복잡한 구현을 요구하지도 않는 문제다.

다만, 인덱스와 범위 설정부분을 주의해서 신중하게 구현할 필요가 있는 문제이다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M, K;
	static int[][] arr;
	static int[][] playerMap;

	static class Point {
		int x;
		int y;

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

	static Point exit;
	static Point[] players;
	static int numPlayer;
	static int[] dist;
	static boolean[] isExit;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, 1, -1};

	public static void main(String[] args) throws Exception {
		// input
		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];
		playerMap = new int[N][N];
		for (int i = 0; i < N; ++i) {
			inputs = in.readLine().split(" ");
			for (int j = 0; j < N; ++j) {
				arr[i][j] = stoi(inputs[j]);
			}
		}
		players = new Point[M];
		for (int i = 0; i < M; ++i) {
			inputs = in.readLine().split(" ");
			int x = stoi(inputs[0]) - 1;
			int y = stoi(inputs[1]) - 1;
			playerMap[x][y] += 1 << i;
			players[i] = new Point(x, y);
		}
		inputs = in.readLine().split(" ");
		exit = new Point(stoi(inputs[0]) - 1, stoi(inputs[1]) - 1);
		numPlayer = M;
		dist = new int[M];
		isExit = new boolean[M];

		for (int t = 0; t < K; ++t) {
			if (numPlayer == 0)
				break;

			// 플레이어의 이동
			movePlayer();
			if (numPlayer == 0)
				break;
			
			// 미로의 회전
			rotateMaze();
		}
		int sum = 0;
		for (int i : dist)
			sum += i;
		StringBuilder sb = new StringBuilder();
		sb.append(sum).append("\n").append(exit.x+1).append(" ").append(exit.y+1);
		System.out.println(sb);
	}

	private static void movePlayer() {
		for (int i = 0; i < M; ++i) {
			// 이미 탈출한 플레이어
			if (isExit[i])
				continue;
			int base = getDistance(exit.x, exit.y, players[i].x, players[i].y);
			int min = Integer.MAX_VALUE;
			int dir = -1;
			for (int d = 0; d < 4; ++d) {
				int nx = players[i].x + dx[d];
				int ny = players[i].y + dy[d];
				// 범위 밖
				if (!isInRange(nx, ny))
					continue;

				int value = getDistance(exit.x, exit.y, nx, ny);

				// 최단거리로만 이동한다. 더 먼 방향으로는 이동X
				if (base < value)
					continue;

				if (arr[nx][ny] > 0)
					continue;

				if (value < min) {
					min = value;
					dir = d;
				}
			}
			// 모든 방향으로 갈 수 없는 상태.
			if (dir == -1)
				continue;

			playerMap[players[i].x][players[i].y] -= 1 << i;
			players[i].x = players[i].x + dx[dir];
			players[i].y = players[i].y + dy[dir];
			playerMap[players[i].x][players[i].y] += 1 << i;
			dist[i]++;

			if (players[i].x == exit.x && players[i].y == exit.y) {
				playerMap[players[i].x][players[i].y] -= 1 << i;
				numPlayer--;
				isExit[i] = true;
			}
		}
	}

	private static void rotateMaze() {
		int len = 0;
		int r = 0;
		int c = 0;
		boolean flag = false;
		for (int length = 2; length <= N; ++length) {
			for (int i = 0; i <= N - length; ++i) {
				for (int j = 0; j <= N - length; ++j) {
					flag = findSquare(i, j, length);
					if (flag) {
						r = i;
						c = j;
						len = length;
						flag = true;
						break;
					}
				}
				if (flag)
					break;
			}
			if (flag)
				break;
		}

		// 회전
		rotate(r, c, len);
	}

	private static void rotate(int r, int c, int len) {
		int[][] copy = new int[len][len];
		int[][] copyPlayer = new int[len][len];
		int nx = 0;
		int ny = 0;
		for (int i = 0; i < len; ++i) {
			for (int j = 0; j < len; ++j) {
				copy[j][len - 1 - i] = arr[i + r][j + c];
				copyPlayer[j][len - 1 - i] = playerMap[i + r][j + c];

				if (exit.x == i + r && exit.y == j + c) {
					nx = j + r;
					ny = len - 1 - i + c;
				}
			}
		}
		exit.x = nx;
		exit.y = ny;
		for (int i = r; i < r + len; ++i) {
			for (int j = c; j < c + len; ++j) {
				arr[i][j] = copy[i - r][j - c];
				if (arr[i][j] > 0)
					arr[i][j]--;

				playerMap[i][j] = copyPlayer[i - r][j - c];
				for (int k = 0; k < M; ++k) {
					int p = 1 << k;
					if ((playerMap[i][j] & p) == p) {
						players[k].x = i;
						players[k].y = j;
					}
				}
			}
		}
	}

	private static boolean findSquare(int i, int j, int length) {
		boolean hasPlayer = false;
		boolean hasExit = false;

		for (int x = i; x < i + length; ++x) {
			for (int y = j; y < j + length; ++y) {
				if (!hasPlayer) {
					if (playerMap[x][y] > 0)
						hasPlayer = true;
				}

				if (!hasExit)
					if (exit.x == x && exit.y == y)
						hasExit = true;

				if (hasPlayer && hasExit)
					return true;
			}
		}
		return false;
	}

	public static boolean isInRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N)
			return true;
		return false;
	}

	public static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}