[삼성 SW 역량평가] 메이즈 러너(C++)

풀이 소요시간 : 약 90분

이 문제는 바로 직전 2023 상반기 삼성 SW 역량평가 오후 1번 문제였다.

골드3 깡구현 문제였지만 200줄 이상 코드가 나올정도로 복잡했고, 나름 모르면 해결하기 어려운 구현도 있었다.
삼성 SW 코테는 주어진 시간동안 1문제 라도 정확하게 풀어서 제출하는 것이 아주 중요하다. 실수만 안했으면 60분정도에 클리어 했을텐데 변수명 하나를 잘못써서 엄청나게 시간을 잡아먹었다. 이런 복잡한 시뮬레이션은 뇌 비우고 코딩하다가는 큰일날 수 있다. 일단 90분동안 한 문제를 풀었으니, 이게 실전이였으면 붙었을지는 미지수다.

까다로운 포인트

참가자, 출구, 미로의 이동을 따로 고려해야 한다는 점

이 점이 초반에 나를 힘들게 했다. 미로의 이동만 하면 나도모르게 출구와 참가자 또한 이동이 된 줄 착각하고 구현을 배제했다. 나는 미로 위에 참가자와 출구를 표기하지 않고 따로 값을 저장하고 있었기 때문에 반드시 따로 이동을 구현해야했다. 하지만 미로 위에 같이 표기했다면 더욱 끔찍한 구현이였을 것이다.

배열의 90도 회전

이거는 내가 비슷한 문제를 풀어본 적이 있어서 쉽게 구현할 수 있었다. 즉석에서 떠올리려면 굉장히 머리가 좋아야 하는 구현이기에, 애초에 혹시 몰라서 외워뒀던게 아주 도움이 됬다.

최적의 사각형 구하기

x, y 좌표와 Ex, Ey 좌표가 존재할 때 두 좌표를 포함하는 정사각형 변의 최소 길이와 좌측 최상단의 좌표를 알아야지 위의 배열 90도 회전까지 연계가 가능하다. 따라서 이걸 모르면 문제를 풀 수 없다. 아래의 코드로 규칙을 찾아낼 수 있었다. 계산 후 mx, my 좌표 값이 1 미만인 경우 1로 수정해주는 Make_Range 의 개념을 적용하는 것이 중요하다.

//정사각형 정보 생성
void Square_Data(int x, int y) {
    int x_Gap = abs(x - Ex);
    int y_Gap = abs(y - Ey);

    int Size = max(x_Gap, y_Gap);

    int mx = max(Ex, x) - Size;
    if (mx < 1) mx = 1;

    int my = max(Ey, y) - Size;
    if (my < 1) my = 1;

    Data.push_back({ mx, my, Size });
}

전체 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int N, M, K;
int Ex, Ey;
int Map[11][11];

int Ans = 0;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

struct Person {
    int x;
    int y;
};

struct Position {
    int x;
    int y;
    int Size;
};

vector<Person> Vector;
vector<Position> Data;

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

    int X;
    int Y;
    for (int i = 1; i <= M; i++)
    {
        cin >> X >> Y;
        Vector.push_back({ X, Y });
    }

    cin >> Ex >> Ey;
}


// 해당 좌표에서 출구까지의 거리
int Dist_Exit(int x, int y) {
    return abs(x - Ex) + abs(y - Ey);
}

//최선의 정사각형 기준 정렬
bool Cmp(Position& A, Position& B) {
    if (A.Size == B.Size)
    {
        if (A.x == B.x)
        {
            return A.y < B.y;
        }
        return A.x < B.x;
    }
    return A.Size < B.Size;
}


// 각 참가자의 이동
void Exit(Person& P) {

    int Curr = Dist_Exit(P.x, P.y);

    //자동 상, 하 우선 탐색
    for (int i = 0; i < 4; i++)
    {
        int nx = P.x + dx[i];
        int ny = P.y + dy[i];
        int Next = Dist_Exit(nx, ny);

        if (nx < 1 || ny < 1 || nx > N || ny > N) continue; //범위 초과
        if (Curr <= Next) continue;                         //이전보다 가까워져야한다.
        if (Map[nx][ny] > 0) continue;                      //빈칸이 아닌 경우 이동 불가.

        Ans++;
        P.x = nx;   //x 좌표 변경
        P.y = ny;   //y 좌표 변경
        break;
    }

}

//정사각형 정보 생성
void Square_Data(int x, int y) {
    int x_Gap = abs(x - Ex);
    int y_Gap = abs(y - Ey);

    int Size = max(x_Gap, y_Gap);

    int mx = max(Ex, x) - Size;
    if (mx < 1) mx = 1;

    int my = max(Ey, y) - Size;
    if (my < 1) my = 1;

    Data.push_back({ mx, my, Size });
}


//사각형을 시계 방향으로 90도 회전한다.
void Rotation(int x, int y, int Size) {

    vector<pair<pair<int, int>, int>> Pair;
    bool Flag = true; //출구 이동 여부

    for (int i = 0; i <= Size; i++)
    {
        for (int j = 0; j <= Size; j++)
        {
            //기존 좌표
            int px = x + i;
            int py = y + j;

            //전환 좌표
            int nx = x + j;
            int ny = y + Size - i;

            //출구가 회전하는 경우
            if (px == Ex && py == Ey && Flag == true)
            {
                Flag = false;
                Ex = nx;
                Ey = ny;
            }

            Pair.push_back({ {nx, ny}, Map[px][py] });
        }
    }

    //기존 값을 새로운 좌표에 도입 + 벽 허물기
    for (auto E : Pair)
    {
        int x = E.first.first;
        int y = E.first.second;
        int m = E.second;
        if (m == 0)
        {
            Map[x][y] = 0;
        }
        else if (m > 0)
        {
            Map[x][y] = m - 1;
        }
    }

    //참가자 회전
    for (auto& E : Vector)
    {
  
        if (E.x >= x && E.x <= x + Size)
        {

            if (E.y >= y && E.y <= y + Size)
            {

                int i = E.x - x;
                int j = E.y - y;

                E.x = x + j;
                E.y = y + Size - i;

            }
        }
    }


}

int main() {
    Input();
    while (K--)
    {

        for (int i = 0; i < Vector.size(); i++)
        {
            Exit(Vector[i]);

            if (Vector[i].x == Ex && Vector[i].y == Ey)
            {
                Vector.erase(Vector.begin() + i);
                i--;
                continue;
            }

            Square_Data(Vector[i].x, Vector[i].y);
        }


        if (Vector.size() == 0) break;


        sort(Data.begin(), Data.end(), Cmp);
        Rotation(Data[0].x, Data[0].y, Data[0].Size);
        Data.clear();

    }

    cout << Ans << '\n';
    cout << Ex << ' ' << Ey << '\n';
}