코드트리 - 메이즈러너

메이즈러너

코드트리 Gold3 Simulation
코드트리 - 메이즈러너

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 풀이

미로의 크기와 참가자들의 위치, 탈출구의 위치가 주어지고 참가자들은 1초에 한칸씩 출구와 가까워 지는 방향으로만 움직일 수 있고 동시에 움직인다.
탈출구에 도착한 참가자는 즉시 탈출하며, 한칸에 여러명의 참가자가 겹칠 수 있고, 동시에 움직인다.

 

동시에 움직이는 조건을 제외하면 루돌프의 반란에서 주어졌던 산타의 움직임과 동일했다.

유클리드 거리가 가까워 지는 방향으로만 움직이고, 벽이 있으면 더이상 가지 못한다.

 

모든 참가자가 이동을 마치면 미로가 회전하는데,
회전하는 부분은 탈출구와 최소 한명의 참가자를 포함하는 가장 작은 부분 정사각형의 형태로 시계방향 90도 회전한다.

 

이 문제 풀이의 가장 핵심이 된다고 생각했던 부분이 90도 회전하는 부분과 맵 일부의 정사각형을 찾는 부분이었다.

 

rotate90Clockwise()

90도 회전 같은 경우에는 솔직히 어떻게 해야할지 감이안와 이것저것 시도해보다가 gpt에게 물어봤다.

다음과 같이 움직일 수 있고,
부분 배열의 경우, 시작점과 끝점을 0, 0 으로 이동시키고 회전한다고 생각하면 됐다.

 

findBoundaryForRoatate()

이 부분이 가장 난해했다.

처음에는 출구와 가장 가까운 참가자 한명씩을 찾고, 해당 참가자와 탈출구의 x, y 좌표의 최대값에서 두 좌표 끼리의 거리 중 큰 값을 뺀 값으로 사용했었다.

그러다보니 문제에서 의도하는 부분과 좀 안맞는 부분이 발생했었고, 고민하다 결국 답을 봤는데
답에서는 문제에서 주어지는 순서대로 정사각형을 탐색하고, 조건을 만족하면 해당 정사각형을 사용하는 방식으로 풀이했다.

주어지는 미로의 크기가 최대 10x10으로 비교적 작고, 참가자 수 또한 10명 정도로 충분히 시간내에 가능하겠다는 생각을 했다.

 

코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <tuple>

using namespace std;

struct runnerInfo {
    int r, c;
    bool isEscape;

    runnerInfo() : r(0), c(0), isEscape(false) {}
};  

vector<vector<int>> maze;
unordered_map<int, runnerInfo> runners;
int N, ret = 0;
int mv[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
pair<int, int> mazeExit;

bool checkBoundary(int x, int y) {
    return x < 0 || x >= N || y < 0 || y >= N;
}

int calDistance (int x, int y, int r, int c) {
    return abs(x - r) + abs(y - c);
}

bool isInBoundary (int x, int y, int sx, int sy, int len) {
    return sx <= x && x < sx+len && sy <= y && y < sy+len;
}

void rotate90Clockwise(int len, int x, int y) {
    vector<vector<int>> tmp = maze;

    for (int i=0; i<len; i++) {
        for (int j=0; j<len; j++) {
            tmp[x+j][y+len-i-1] = maze[x+i][y+j];
            if (tmp[x+j][y+len-i-1] > 0) tmp[x+j][y+len-i-1]--;
        }
    }

    for (auto p: runners) {

        if (!p.second.isEscape && isInBoundary(p.second.r, p.second.c, x, y, len)) {      
            int ox = p.second.r - x, oy = p.second.c - y;
            int i = oy + x;
            int j = len - ox - 1 + y;

            runners[p.first].r = i;
            runners[p.first].c = j;
        }
    }

    int ox = mazeExit.first - x, oy = mazeExit.second - y;

    int i = oy + x;
    int j = len - ox - 1 + y;

    mazeExit.first = i;
    mazeExit.second = j;

    maze = tmp;
}

tuple<int, int, int> findSubArryForRotate() {

    for (int len=2; len<=N; len++) {
        for (int i=0; i<N-len+1; i++) {
            for (int j=0; j<N-len+1; j++) {
                if (!isInBoundary(mazeExit.first, mazeExit.second, i, j, len)) continue;

                for (auto p: runners) {
                    if (p.second.isEscape) continue;
                    if (isInBoundary(p.second.r, p.second.c, i, j, len)) {
                        return make_tuple(len, i, j);
                    }
                }
            }
        }
    }

    return make_tuple(0, 0, 0);
}

void runnerMoving() {
    for (auto p: runners) {
        if (p.second.isEscape) continue;
        pair<int, int> res;

        int x = p.second.r;
        int y = p.second.c;
        res.first = calDistance(x, y, mazeExit.first, mazeExit.second);
        res.second = 5;

        for (int i=0; i<4; i++) {
            int dx = x + mv[i][0];
            int dy = y + mv[i][1];
            if (checkBoundary(dx, dy) || maze[dx][dy] > 0) continue;
            int dist = calDistance(dx, dy, mazeExit.first, mazeExit.second);
            if (res.first > dist) {
                res.first = dist;
                res.second = i;
            }
        }

        if (res.second == 5) continue;

        runners[p.first].r += mv[res.second][0];
        runners[p.first].c += mv[res.second][1];
        ret++;
        if (runners[p.first].r == mazeExit.first && runners[p.first].c == mazeExit.second)
            runners[p.first].isEscape = true;
    }
    return ;
}

bool rotateMaze() {
    tuple<int, int, int> tp;
    tp = findSubArryForRotate();

    if (!get<0>(tp)) return false;

    rotate90Clockwise(get<0>(tp), get<1>(tp), get<2>(tp));

    return true;
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int M, K, r, c;
    cin >> N >> M >> K;
    maze.resize(N, vector<int>(N, 0));

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> maze[i][j];
        }
    }

    for (int i=1; i<=M; i++) {
        runnerInfo tmp;
        cin >> tmp.r >> tmp.c;
        tmp.r--;
        tmp.c--;
        runners[i] = tmp;
    }
    cin >> mazeExit.first >> mazeExit.second;
    mazeExit.first--;
    mazeExit.second--;

    for (int i=0; i<K; i++) {
        runnerMoving();
        if (!rotateMaze()) break;
    }

    cout << ret << "\n";
    cout << mazeExit.first << " " << mazeExit.second << "\n";

    return 0;   
}

 

회고

문제에 나타나는 조건 뿐만 아니라, 주어지는 크기를 고려하여 시간복잡도를 고려해 풀이해야했던 문제였다.

이전에 왕실의 기사 대결을 풀 때도 느낀거지만 때로는 가장 단순하게 접근하는게 도움이 될 때도 있는 것 같다.