메이즈 러너 [2023-상반기 오후 1번 문제]
문제 링크
삼성 코딩테스트 기출 문제: 메이즈 러너 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
문제 설명
M명의 참가자가 미로를 탈출해야 함. N*N크기의 격자이고, 빈칸, 벽, 출구로 구분되어 있음.
1초마다 참가자는 한 칸씩 움직임. 움직이는 거리는 최단거리 abs(x1-x2) + abs(y1-y2) 로 움직임. 벽이 없는 곳으로 움직일 수 있고, 현재 머물러 있던 칸보다 최단거리가 가까워야 함. 움직일 수 있는 칸이 2칸 이상이라면, 상하로 움직이는 것을 선호함. 움직일 수 없으면, 움직이지 않음.
모든 참가자가 이동을 끝냈으면, 미로가 90도 회전함. 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 잡음. 가장 작은 크기를 같은 정사각형이 2개 이상이라면 행-열 순으로 좌표가 작은 것이 우선시됨.
K초 동안 위의 과정이 반복되고, K초 전에 모든 참가자가 탈출을 성공한다면, 게임이 끝남. 모든 참가자들의 이동 거리의 합과 출구 좌표 출력
해결 방법
- 참가자들 움직임현재 위치보다 더 작은 값으로 이동 할 수 있는 값이 있다면, 해당 위치로 이동. 해당 위치가 출구라면 해당 참가자가 탈출했음을 표시.
for (int r = 0;r < m;r++) {
if (runner[r].escaped) continue;
int d = -1;
int cur_d = get_distance(runner[r].x,runner[r].y);
for (int i = 0;i < 4;i++) {
int nx, ny;
nx = runner[r].x + dx[i], ny = runner[r].y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny]) continue;
if (cur_d > get_distance(nx, ny)) {
cur_d = get_distance(nx, ny);
d = i;
}
}
if (d == -1) continue;
// if (arr[runner[r].x + dx[d]][runner[r].y + dy[d]]) continue;
runner[r].x += dx[d], runner[r].y += dy[d];
if (runner[r].x == ex && runner[r].y == ey) {
runner[r].escaped = true;
runner_cnt--;
if (runner_cnt == 0) {
move_cnt++;
return;
}
}
move_cnt++;
}
- 미로 회전미로가 회전해야 하는 좌상단, 그리고 길이를 찾음.
int lx, ly;
bool can_break = false;
int ssx, ssy, eex, eey;
for (int p = 1;p < n;p++) {
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
lx = i + 1 * p; ly = j + 1 * p;
if (lx < 0 || ly < 0 || lx >= n || ly >= n) continue;
if (contains_runner_escape(i, j, p)) {
can_break = true;
ssx = i, ssy = j, eex = lx, eey = ly;
break;
}
}
if (can_break) break;
}
if (can_break) break;
}
그리고 미로를 회전시켜줌.
int tmp[11][11];
void rotate(int len) {
int ttmp[11][11];
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
ttmp[i][j] = tmp[len - j - 1][i];
}
}
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = ttmp[i][j];
}
}
}
void rotate_square(int sx,int sy,int lx, int ly) {
memset(tmp, 0, sizeof(tmp));
int len = abs(sx - lx) + 1;
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = arr[i+sx][j+sy];
}
}
rotate(len);
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
arr[i + sx][j + sy] = tmp[i][j];
if (arr[i + sx][j + sy] > 0) arr[i + sx][j + sy]--;
}
}
memset(tmp, 0, sizeof(tmp));
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = runner_map[i + sx][j + sy];
}
}
rotate(len);
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
runner_map[i + sx][j + sy] = tmp[i][j];
}
}
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
for (int k = 0;k < m;k++) {
if (runner[k].cur == runner_map[i + sx][j + sy]) {
runner[k].x = i + sx, runner[k].y = j + sy;
}
else if (runner_map[i + sx][j + sy] == -1) {
ex = i + sx, ey = j + sy;
}
}
}
}
}
전체 코드
#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
typedef struct {
int x, y;
int cur;
bool escaped;
}_loc;
int n, m, k;
int ex, ey;
int arr[11][11];
int runner_map[11][11];
int runner_cnt;
_loc runner[11];
void input() {
cin >> n >> m >> k;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cin >> arr[i][j];
}
}
for (int i = 0;i < m;i++) {
cin >> runner[i].x >> runner[i].y;
runner[i].x--, runner[i].y--;
runner[i].escaped = false;
}
runner_cnt = m;
cin >> ex >> ey;
ex--, ey--;
}
int dx[4] = { -1,1, 0,0 };
int dy[4] = { 0, 0, 1, -1 };
int visited[11][11];
_loc parent[11][11];
void set_runner_map() {
memset(runner_map, 0, sizeof(runner_map));
for (int i = 0;i < m;i++) {
if (runner[i].escaped) continue;
if (runner_map[runner[i].x][runner[i].y] == 0) {
runner_map[runner[i].x][runner[i].y] = i + 1;
runner[i].cur = i + 1;
}
else {
runner[i].cur = runner_map[runner[i].x][runner[i].y];
}
}
runner_map[ex][ey] = -1;
}
void print_arr() {
int tmp_arr[11][11];
memset(tmp_arr, 0, sizeof(tmp_arr));
for (int i = 0;i < m;i++) {
if (runner[i].escaped) continue;
tmp_arr[runner[i].x][runner[i].y] = 1;
}
cout << "print_arr:\\n";
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (tmp_arr[i][j]) cout << "# ";
else if (i == ex && j == ey) cout << "@ ";
else cout << arr[i][j] << " ";
}
cout << "\\n";
}
cout << "\\n";
}
int get_distance(int x, int y) {
return abs(x - ex) + abs(y - ey);
}
bool contains_runner_escape(int sx,int sy,int p) {
bool can_escape = false;
bool can_runner = false;
int cx, cy;
for (int i = 0;i <= p;i++) {
for (int j = 0;j <= p;j++) {
cx = i + sx, cy = j + sy;
if (cx == ex && cy == ey) can_escape = true;
if (runner_map[cx][cy] && runner_map[cx][cy] != -1) {
can_runner = true;
}
}
}
if (can_escape && can_runner) return true;
return false;
}
int tmp[11][11];
void rotate(int len) {
int ttmp[11][11];
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
ttmp[i][j] = tmp[len - j - 1][i];
}
}
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = ttmp[i][j];
}
}
}
void rotate_square(int sx,int sy,int lx, int ly) {
memset(tmp, 0, sizeof(tmp));
int len = abs(sx - lx) + 1;
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = arr[i+sx][j+sy];
}
}
rotate(len);
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
arr[i + sx][j + sy] = tmp[i][j];
if (arr[i + sx][j + sy] > 0) arr[i + sx][j + sy]--;
}
}
memset(tmp, 0, sizeof(tmp));
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
tmp[i][j] = runner_map[i + sx][j + sy];
}
}
rotate(len);
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
runner_map[i + sx][j + sy] = tmp[i][j];
}
}
for (int i = 0;i < len;i++) {
for (int j = 0;j < len;j++) {
for (int k = 0;k < m;k++) {
if (runner[k].cur == runner_map[i + sx][j + sy]) {
runner[k].x = i + sx, runner[k].y = j + sy;
}
else if (runner_map[i + sx][j + sy] == -1) {
ex = i + sx, ey = j + sy;
}
}
}
}
}
int move_cnt = 0;
void solve(int t) {
// 1. 참가자 움직임
for (int r = 0;r < m;r++) {
if (runner[r].escaped) continue;
int d = -1;
int cur_d = get_distance(runner[r].x,runner[r].y);
for (int i = 0;i < 4;i++) {
int nx, ny;
nx = runner[r].x + dx[i], ny = runner[r].y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny]) continue;
if (cur_d > get_distance(nx, ny)) {
cur_d = get_distance(nx, ny);
d = i;
}
}
if (d == -1) continue;
// if (arr[runner[r].x + dx[d]][runner[r].y + dy[d]]) continue;
runner[r].x += dx[d], runner[r].y += dy[d];
if (runner[r].x == ex && runner[r].y == ey) {
runner[r].escaped = true;
runner_cnt--;
if (runner_cnt == 0) {
move_cnt++;
return;
}
}
move_cnt++;
}
set_runner_map();
// 2. 미로 회전
int lx, ly;
bool can_break = false;
int ssx, ssy, eex, eey;
for (int p = 1;p < n;p++) {
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
lx = i + 1 * p; ly = j + 1 * p;
if (lx < 0 || ly < 0 || lx >= n || ly >= n) continue;
if (contains_runner_escape(i, j, p)) {
can_break = true;
ssx = i, ssy = j, eex = lx, eey = ly;
break;
}
}
if (can_break) break;
}
if (can_break) break;
}
if (!can_break) {
cout << "error!\\n";
print_arr();
exit(0);
}
rotate_square(ssx,ssy,eex,eey);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("sample_input.txt", "r", stdin);
input();
// print_arr();
for (int i = 0;i < k;i++) {
solve(i);
// print_arr();
if (runner_cnt == 0) break;
}
cout << move_cnt << "\\n" << ex + 1 << " " << ey + 1;
}