메이즈 러너

Simulation, Exhaustive Search

• 평균 : 180'

---

sol : 171' 26''

• 수행 시간 : 9ms
• 메모리 : 0MB

Learnings

• 피곤할 땐 차라리 쉬자.
• 그리드 내 임의의 영역에서 좌표 회전

정사각형의 좌상단을 (i, j)라 하자.
struct Square {
	// r : 정사각형의 길이
    int r, i, j;
};

bool is_in(int _i, int _j) const {
    return i <= _i && _i < i + r && j <= _j && _j < j + r;
}

어떤 점이 이 정사각형 내부에 존재할 때, 이 점의 좌표를 (_i, _j)라 하자.

정사각형 내부에서의 절대 좌표
int row = _i - i;
int col = _j - j;
회전 : (row, col) -> (col, r - 1 - row);

new_i = i + col = i + (_j - j);
new_j = j + (r - 1 - row) = j + (r - 1 - (_i - i));

즉, 정리하면
new_i = i + _j - j;
new_j = j + r - 1 - (_i - i)
->
new_i = square.i + (old_j - square.j);
new_j = square.j + square.r - 1 - (old_i - square.i);

가 되는 것이다.

이를 활용하여 아래와 같이 구현했다.
여기서도 그리드에 출구나 사람을 표시하지 않고 직접 변환해준다.

if (square.is_in(pos_exit_i, pos_exit_j)) {
    int next_i = square.rotated_i(pos_exit_j);
    int next_j = square.rotated_j(pos_exit_i);
    pos_exit_i = next_i;
    pos_exit_j = next_j;
}

for (auto& person : people) {
    if (square.is_in(person.i, person.j)) {
        int next_i = square.rotated_i(person.j);
        int next_j = square.rotated_j(person.i);
        person.i = next_i;
        person.j = next_j;
    }
}

벽도 이렇게 바꿨네

for (auto& wall : walls) {
    if (square.is_in(wall.i, wall.j)) {
        int next_i = square.rotated_i(wall.j);
        int next_j = square.rotated_j(wall.i);
        wall.i = next_i;
        wall.j = next_j;
    }
}

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <cmath>

using namespace std;

#define EMPTY 0
#define EXITHOLE -1
#define MAX_N 11
#define MAX_M 11

int n, m, k;
int second;
bool finished;
int grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

struct Player {
	int i;
	int j;
	int movedDist;
	bool escaped;

	Player() {}
	Player(int _i, int _j, int _movedDist, bool _escaped) :
		i(_i), j(_j), movedDist(_movedDist), escaped(_escaped) { }
};

vector<Player> players;
pair<int, int> exitIdx;

void Init() {
	cin >> n >> m >> k;

	players.resize(MAX_M);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}

	for (int p = 1; p <= m; p++) {
		int r, c;
		cin >> r >> c;
		players[p] = { r, c, 0, false };
	}

	int r, c;
	cin >> r >> c;
	exitIdx = make_pair(r, c);
	grid[r][c] = EXITHOLE;
}

void DebugGrid(int g[MAX_N][MAX_N]) {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

int DistToExit(int i, int j) {
	return abs(i - exitIdx.first) + abs(j - exitIdx.second);
}

void InitVisited() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

pair<int, int> GetNextStep(Player p) {
	int ci = p.i, cj = p.j;
	pair<int, int> nextStep = { -1, -1 };

	for (int d = 0; d < 4; d++) {
		int ni = ci + ds[d][0], nj = cj + ds[d][1];

		if (InGrid(ni, nj) && (grid[ni][nj] == EMPTY || grid[ni][nj] == EXITHOLE)) {
			if (DistToExit(ci, cj) > DistToExit(ni, nj)) {
				nextStep = { ni, nj };
				return nextStep;
			}
		}
	}

	return nextStep;
}

void EscapeCheck(int p) {
	if (players[p].i == exitIdx.first && players[p].j == exitIdx.second) {
		players[p].escaped = true;
	}
}

void Move() {
	for (int p = 1; p <= m; p++) {
		if (players[p].escaped) continue;

		int ni, nj;
		tie(ni, nj) = GetNextStep(players[p]);
		
		if (ni == -1) continue;

		players[p].i = ni;
		players[p].j = nj;
		
		players[p].movedDist++;

		EscapeCheck(p);
	}
}

tuple<int, int, int> GetMinSquare() {
	// 한 변의 길이가 2인 정사각형부터 n인 정사각형까지
	for (int size = 2; size <= n; size++) {
		// 시작점 설정
		for (int i = 1; i <= n - size + 1; i++) {
			for (int j = 1; j <= n - size + 1; j++) {
				bool exitExist = false;
				bool playerExist = false;

				// 정사각형 영역 설정
				for (int di = i; di < i + size; di++) {
					for (int dj = j; dj < j + size; dj++) {
						if (di == exitIdx.first && dj == exitIdx.second) {
							exitExist = true;
						}
						for (int p = 1; p <= m; p++) {
							if (players[p].escaped) continue;
							if (players[p].i == di && players[p].j == dj) {
								playerExist = true;
							}
						}
					}
				}

				if (exitExist && playerExist) {
					return make_tuple(i, j, size);
				}
			}
		}
	}

	return make_tuple(-1, - 1, - 1);
}

void Rotate(int si, int sj, int size) {
	int temp1[MAX_N][MAX_N];
	int temp2[MAX_N][MAX_N];
	vector<tuple<int, int, int>> changedPlayers;

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			temp1[i][j] = grid[si + i][sj + j];
			for (int p = 1; p <= m; p++) {
				if (players[p].escaped) continue;
				if (players[p].i == si + i && players[p].j == sj + j) {
					changedPlayers.push_back(make_tuple(p, si + i, sj + j));
				}
			}
		}
	}

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			temp2[j][size - i - 1] = temp1[i][j];
		}
	}

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			grid[si + i][sj + j] = temp2[i][j];
			
			if (grid[si + i][sj + j] > 0) {
				grid[si + i][sj + j]--;
			}
			else if (grid[si + i][sj + j] == EXITHOLE) {
				exitIdx = make_pair(si + i, sj + j);
			}
		}
	}

	for (int i = 0; i < changedPlayers.size(); i++) {
		int p, r, c;
		tie(p, r, c) = changedPlayers[i];

		r -= si, c -= sj;

		players[p].i = si + c;
		players[p].j = sj + size - r - 1;
	}
}

void Rotation() {
	// 출구와 참가자 최소 1명을 포함한 가장 작은 정사각형 찾기
	int si, sj, size;
	tie(si, sj ,size) = GetMinSquare();

	if (si == -1) {
		return;
	}
	else {
		Rotate(si, sj, size);
	}
}

void PrintAnswer() {
	int totalDist = 0;
	for (int p = 1; p <= m; p++) {
		totalDist += players[p].movedDist;
	}

	cout << totalDist << '\n';
	cout << exitIdx.first << ' ' << exitIdx.second;
}

int main() {
	Init();

	while (!finished && ++second <= k) {
		// 1. 1초마다 모든 참가자는 한 칸씩, 동시에 움직인다.
		Move();

		// 2. 미로가 회전한다.
		Rotation();
	}

	PrintAnswer();

	return 0;
}