[코드트리] 메이즈 러너 - c++

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text

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

 

중요포인트

 

행과 열을 헷갈리지 말자!!

 

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <iomanip>

using namespace std;

struct Player {
    int y, x, howmany;
};

int N, M, K, exitY, exitX, maze[11][11], player[11][11], dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 }, totalDis = 0;

void printMaze() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << setw(3) << maze[i][j];
        }
        cout << "\n";
    }
}

bool oob(int y, int x) {
    return y < 1 || x < 1 || y > N || x > N;
}

void rotate(tuple<int, int, int> pointWithSize) {
    int size = get<2>(pointWithSize);
    vector<vector<int>> tmp(size + 1, vector<int>(size + 1, 0));
    int row = get<0>(pointWithSize), col = get<1>(pointWithSize);

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            tmp[j][size - i + 1] = maze[row + i - 1][col + j - 1];
            if (tmp[j][size - i + 1] > 0) tmp[j][size - i + 1]--;
        }
    }

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            maze[row + i - 1][col + j - 1] = tmp[i][j];
        }
    }
}

tuple<int, int, int> findSmallSqure() {
    tuple<int, int, int> pointWithSize;
    int eY, eX;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            }
        }
    }

    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++) {
                int peopleCount = 0;
                bool hasExit = false;

                for (int row = i; row < i + size; row++) {
                    for (int col = j; col < j + size; col++) {
                        if (maze[row][col] == -11) hasExit = true;
                        else if (-10 <= maze[row][col] && maze[row][col] <= -1) peopleCount += -1 * maze[row][col];
                    }
                }

                if (hasExit && peopleCount >= 1) {
                    pointWithSize = {i, j, size};
                    return pointWithSize;
                }
            }
        }
    }
    return pointWithSize;
}

void move() {
    int eY, eX, tmp[21][21];
    queue<pair<int, int>> q;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            tmp[i][j] = 0;
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            } else if (maze[i][j] <= -1 && -10 <= maze[i][j]) {
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        int curY = q.front().first, curX = q.front().second;
        q.pop();
        int moveY = 0, moveX = 0, exitDis = abs(eY - curY) + abs(eX - curX);

        for (int d = 0; d < 4; d++) {
            int ny = curY + dy[d], nx = curX + dx[d];
            if (oob(ny, nx) || maze[ny][nx] > 0) continue;
            int dis = abs(ny - eY) + abs(nx - eX) + 1;
            if (exitDis < dis) continue;
            else if (exitDis == dis) {
                if ((eY - curY > 0 && ny - curY > 0) || (eY - curY < 0 && ny - curY < 0) || maze[ny][nx] == -11) {
                    moveY = ny;
                    moveX = nx;
                } else if (moveY == 0) {
                    moveY = ny;
                    moveX = nx;
                }
            }
        }

        if (moveY != 0) {
            totalDis += maze[curY][curX] * -1;
            if (maze[moveY][moveX] != -11) tmp[moveY][moveX] += maze[curY][curX];
            maze[curY][curX] = 0;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (tmp[i][j] != 0) maze[i][j] += tmp[i][j];
        }
    }
}

bool isAllEmpty() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (-10 <= maze[i][j] && maze[i][j] <= -1) return false;
        }
    }
    return true;
}

int main() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> maze[i][j];
        }
    }

    for (int i = 0; i < M; i++) {
        int y, x;
        cin >> y >> x;
        maze[y][x] -= 1;
    }

    cin >> exitY >> exitX;
    maze[exitY][exitX] = -11;

    while (K--) {
        if (isAllEmpty()) break;
        move();
        tuple<int, int, int> pointWithSize = findSmallSqure();
        rotate(pointWithSize);
    }

    cout << totalDis << "\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) cout << i << " " << j;
        }
    }
    return 0;
}