메이즈 러너

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20 

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

 

1. 참가자 수 최대 10명

player wichi[11];

 

void move(player& p)

우선순위 : 상 하 좌 우

-> 우선 순위 순서대로 dx, dy를 만든다!

int ima = dist(p.row, p.col);

int tsugi = dist(nx, ny)

ima > tsugi면 이동 후 break

 

2. 이 문제에서 가장 어려웠던 것은

정사각형 구하기이다.

 

근데, 미로 크기가 작으니까

N: 미로의 크기 (4≤N≤10)

 

그냥 (1,1)부터 크기 2 정사각형부터

쫘아아아악 펼쳐서 출구와 player를 포함하면

제일 왼쪽 좌표 두 개랑 크기를 구조체에 넣고

조건 can_make 함수를 통과한다면

break 해주자.

이렇게 하면 벡터 정렬과 cmp 함수를 쓰지 않아도 된다.

 

2. 배열 돌리기

memcpy를 썼다

memcpy(ctrl + v 하는 배열, ctrl + c 하는 배열, sizeof(배열))

 

플레이어는 10을 넣고, 출구는 -1을 넣었다.

 

이중 for문에 변수 4개를 넣고

간단하게 시계방향 90도 회전을 구할 수 있다.

 

3. 

한 칸에 2명 이상의 참가자 

-> 벡터 이차원 배열

배열 돌리기와 벡터 이차원 배열 돌리기를 같이 하자.

 

4. linking 에러

디버깅을 하면서 map 바뀌는 것을 계속 출력시키니까

visual studio가 안되면서 linking 에러가 나왔다.

해결 방법 알아두자.

https://skyjwoo.tistory.com/entry/visual-studio-LNK1168-%EC%93%B0%EA%B8%B0%EC%9A%A9%EC%9C%BC%EB%A1%9C-%EC%97%B4-%EC%88%98-%EC%97%86%EC%8A%B5%EB%8B%88%EB%8B%A4-%EC%98%A4%EB%A5%98

visual studio LNK1168: 쓰기용으로 열 수 없습니다 오류

 

<소스 코드>

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int ans = 0;
int n, m, k;
bool chk[15][15];
int map[15][15];
int r_map[15][15];
 
// 상 하가 우선시
int dx[] = { -1, 1, 0 ,0 };
int dy[] = { 0, 0, -1, 1 };
 
// 출구 위치
int e_x, e_y;
 
inline int dist(int x, int y)
{
    return abs(x - e_x) + abs(y - e_y);
}
 
struct player
{
    int row;
    int col;
    bool finished;
};
 
player wichi[11];
 
void move(player& p)
{
    int ima = dist(p.row, p.col);
 
    for (int k = 0; k < 4; k++)
    {
        int nx = p.row + dx[k];
        int ny = p.col + dy[k];
        int tsugi = dist(nx, ny);
 
        // 범위 벗어나거나, 거리가 안작아지거나, 벽이면
        if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
        if (ima <= tsugi) continue;
        if (map[nx][ny] > 0) continue;
 
        ans++;
        p.row = nx;
        p.col = ny;
        // 상 하 좌 우로 만들어 놨기 때문에
        // 이동 할 수 있다면 바로 break 가능!
        break;
    }
}
 
struct sagak
{
    int byun;
    int jwa_row;
    int jwa_col;
};
 
sagak syurui;
 
bool can_make(int x, int y, int kugi)
{
    bool h_flag = false;
    bool e_flag = false;
    for (int i = x; i < x + kugi; i++)
    {
        for (int j = y; j < y + kugi; j++)
        {
            // 범위 벗어남
            if (i > n || j > n)
                return false;
 
            // 참가자 有
            if (chk[i][j] == true)
                h_flag = true;
            // 출구 有
            if (i == e_x && j == e_y)
                e_flag = true;
        }
    }
 
    if (h_flag == true && e_flag == true)
        return true;
    else
        return false;
}
 
// 가장 작은 정사각형 만들기
// 크기 같은게 여러 개라면
// r, c 작은게 우선
void make_square()
{
    // 참가자 있는지 알려주는 배열
    memset(chk, false, sizeof(chk));
 
    // 가장 작은 정사각형은 
    // 2 x 2 짜리 정사각형이므로
    // 2부터 출발
    int kugi = 2;
 
    for (int i = 1; i <= m; i++)
    {
        if (wichi[i].finished)
            continue;
 
        chk[wichi[i].row][wichi[i].col] = true;
    }
 
    while (true)
    {
        for (int i = 1; i <= n - kugi + 1; i++)
        {
            for (int j = 1; j <= n - kugi + 1; j++)
            {
                // 참가자와 출구를 포함하고 있는지 확인
                if (can_make(i, j, kugi))
                {
                    syurui = { kugi, i, j };
                    return;
                }
            }
        }
        // 없다면 3 x 3, 4 x 4, ... 이렇게 늘려간다.
        kugi++;
    }
    return;
}
 
void rotate(int sx, int sy, int dx, int dy)
{
    memcpy(r_map, map, sizeof(map));
 
    vector<int> people_map[15][15];
 
    for (int i = 1; i <= m; i++)
    {
        if (wichi[i].finished)
            continue;
 
        people_map[wichi[i].row][wichi[i].col].push_back(i);
        r_map[wichi[i].row][wichi[i].col] = 10;
    }
 
    vector<int> people_tmp[15][15];
 
    // 출구는 -1로 설정
    r_map[e_x][e_y] = -1;
    int tmp[15][15] = { 0, };
 
    // 배열 돌리기
    for (int j = dy, p_x = sx; j >= sy; j--, p_x++)
    {
        for (int i = sx, p_y = sy; i <= dx; i++, p_y++)
        {
            people_tmp[i][j] = people_map[p_x][p_y];
            tmp[i][j] = r_map[p_x][p_y];
        }
    }
 
    for (int i = sx; i <= dx; i++)
    {
        for (int j = sy; j <= dy; j++)
        {
            if (people_tmp[i][j].size() == 0)
                continue;
 
            for (int k = 0; k < people_tmp[i][j].size(); k++)
            {
                wichi[people_tmp[i][j][k]].row = i;
                wichi[people_tmp[i][j][k]].col = j;
            }
        }
    }
 
    // map에 다시 그리기 (벽 숫자 감소)
    for (int i = sx; i <= dx; i++)
    {
        for (int j = sy; j <= dy; j++)
        {
            if (tmp[i][j] == 10)
                map[i][j] = 0;
            else if (tmp[i][j] == -1)
            {
                e_x = i;
                e_y = j;
                map[i][j] = 0;
            }
            else if (tmp[i][j] > 0)
            {
                map[i][j] = tmp[i][j] - 1;
            }
            else
            {
                map[i][j] = tmp[i][j];
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        wichi[i] = { a,b, false };
    }
 
    cin >> e_x >> e_y;
 
    for (int t = 0; t < k; t++)
    {
        for (int i = 1; i <= m; i++)
        {
            if (wichi[i].finished)
                continue;
 
            move(wichi[i]);
 
            if (wichi[i].row == e_x && wichi[i].col == e_y)
            {
                wichi[i].finished = true;
                continue;
            }
        }
 
        bool talchul = true;
        for (int i = 1; i <= m; i++)
        {
            if (!wichi[i].finished) {
                talchul = false;
                break;
            }
        }
 
        if (talchul)
            break;
 
        make_square();
 
        int sx = syurui.jwa_row;
        int sy = syurui.jwa_col;
        int dx = sx + syurui.byun - 1;
        int dy = sy + syurui.byun - 1;
 
        rotate(sx, sy, dx, dy);
    }
 
    cout << ans << '\n';
    cout << e_x << ' ' << e_y << '\n';
    return 0;
}