16985 Maaaaaaaaaze

문제 링크

판을 뒤섞을 수 있다는 문제의 조건을 읽지 않아 푸는데 오래걸렸다..

문제를 풀때는 문제를 잘 읽어야 한다

다른 사람의 풀이의 좋은 아이디어

• 12345로 구성된 판과 역순의 54321로 구성된 경로의 판의 최단거리는 같다는 점을 이용해 중복된 검사를 하지 않도록 하였다.
• 출구에서 나갈 수 없으면 경로를 확인하지 않음
• 최소값이 12임을 활용하여 12가 나오면 더이상 검사하지 않음
• 입구에서 들어 갈 수 없으면 경로를 확인하지 않음
• 판의 순서와 역순의 기록한 중복확인용 다차원 배열
• 5!의 순열을 저장한 다차원 배열(좋은 것 같지는 않다.)

내 풀이

#define _CRT_SECURE_NO_WARNINGS

#include <ctime>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

static int INF = 987654321;
int maze[7][7][7], ori_maze[7][7][7];
int used[7], order[5];

struct pos
{
    int x, y, z, mv;
};

void rotate(int idx)
{
    int t[5][5];
    for (int y = 0; y < 5; y++)
        for (int x = 0; x < 5; x++)
            t[x][4 - y] = maze[idx][y + 1][x + 1];
    for (int y = 0; y < 5; y++)
        for (int x = 0; x < 5; x++)
            maze[idx][y + 1][x + 1] = t[y][x];
}

int findWayOut()
{
    if (maze[1][1][1] == 0)
        return INF;
    // z, y, x
    int d[6][3] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };
    int fp[7][7][7];
    queue<pos> que;

    que.push({ 1, 1, 1, 0 });
    memset(fp, 0, sizeof(fp));

    fp[1][1][1] = 1;

    while (!que.empty())
    {
        pos fr = que.front();
        que.pop();
        if (fr.x == 5 && fr.y == 5 && fr.z == 5)
            return fr.mv;

        for (int i = 0; i < 6; i++)
        {
            pos n = fr;
            n.z += d[i][0];
            n.y += d[i][1];
            n.x += d[i][2];
            n.mv += 1;
            if (!maze[n.z][n.y][n.x] || fp[n.z][n.y][n.x])
                continue;

            fp[n.z][n.y][n.x] = 1;
            que.push(n);
        }
    }

    return INF;
}

int permu(int idx)
{
    if (idx == 6)
    {
        return findWayOut();
    }

    int ret = INF, n = 4;
    while (n)
    {
        int t = permu(idx + 1);
        rotate(idx);
        ret = min(t, ret);

        n -= 1;
    }


    rotate(idx);

    return ret;
}

int boardPermu(int idx)
{
    if (idx == 5)
    {
        for (int i = 0; i < 5; i++)
        {
            memcpy(maze[i + 1], ori_maze[order[i]], sizeof(ori_maze[0]));
        }
        return permu(1);
    }
    int ret = INF;
    for (int i = 1; i <= 5; i++)
    {
        if (used[i])
            continue;
        used[i] = 1;
        order[idx] = i;
        ret = min(ret, boardPermu(idx + 1));
        if (ret == 12)
            return ret;
        used[i] = 0;
    }

    return ret;
}

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

    //test
    clock_t st, ed;

    for (int z = 1; z <= 5; z++)
    {
        for (int y = 1; y <= 5; y++)
        {
            for (int x = 1; x <= 5; x++)
            {
                cin >> ori_maze[z][y][x];
            }
        }
    }

    st = clock();

    int ans = boardPermu(0);

    if (ans == INF)
        cout << -1 << "\n";
    else
        cout << ans << "\n";

    ed = clock();

    cout << ed - st << "\n";

    return 0;
}

다른사람 풀이

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int map[4][5][5][5];
int panorder[120][5]; // [5]에 들어가는 값의 범위는 1 ~ 5, 120 5!
int pan[5][5][5][5][5]; //판 중복 체크(입구->출구 == 출구->입구)
int pcnt;
int vis[5];
int chc[5];
int ro[5];
int best = -1;
int qcheck[5][5][5];

struct coor {
    int x;
    int y;
    int z;
    int d;
};

queue<coor> q;
int dx[6] = { 1,0,0,-1,0,0 };
int dy[6] = { 0,1,0,0,-1,0 };
int dz[6] = { 0,0,1,0,0,-1 };

void dfs(int pos) {
    if (pos == 5) {
        for (int i = 0; i < 5; i++)
            panorder[pcnt][i] = vis[i] - 1;
        pcnt++;
        return;
    }
    for (int i = 1; i <= 5; i++) {
        if (chc[i] != 0)
            continue;
        vis[pos] = i;
        chc[i] = 1;
        dfs(pos + 1);
        vis[pos] = 0;
        chc[i] = 0;
    }
}

void bfs(int dfsnumber) {
    memset(qcheck, 0, sizeof(qcheck));
    int x, y, z, nx, ny, nz, d;
    q.push({ 0,0,0,0 });
    qcheck[0][0][0] = 1;
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        z = q.front().z;
        d = q.front().d;
        q.pop();
        if (x == 4 && y == 4 && z == 4) {
            if (best == -1 || (best != -1 && best > d)) {
                best = d;
                if (d == 12) return;
            }
        }
        if (best != -1 && d + 1 >= best) continue;
        for (int i = 0; i < 6; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            nz = z + dz[i];
            if (nx < 0 || ny < 0 || nz < 0 || nx >= 5 || ny >= 5 || nz >= 5) continue;
            if (qcheck[nz][ny][nx] == 1 || map[ro[nz]][panorder[dfsnumber][nz]][ny][nx] == 0) continue;
            qcheck[nz][ny][nx] = 1;
            q.push({ nx,ny,nz,d + 1 });
        }
    }
}

int main(void) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 5; k++)
                cin >> map[0][i][j][k];

    // map[회전][판][행][열]
    // map[0] : 0회전,  map[1] : 1회전, map[2] : 2회전
    for (int i = 1; i <= 3; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                for (int g = 0; g < 5; g++) {
                    map[i][j][4 - g][k] = map[i - 1][j][k][g];
                }
            }
        }
    }
    dfs(0); // set panoder 12345 ~ 54321

    for (int i = 0; i < pcnt; i++) {
        if (pan[panorder[i][0]][panorder[i][1]][panorder[i][2]][panorder[i][3]][panorder[i][4]] == 0) {
            pan[panorder[i][0]][panorder[i][1]][panorder[i][2]][panorder[i][3]][panorder[i][4]] = 1; // 입구 -> 출구
            pan[panorder[i][4]][panorder[i][3]][panorder[i][2]][panorder[i][1]][panorder[i][0]] = 1; // 출구 -> 입구
            for (int fiv = 0; fiv < 4; fiv++) {
                ro[4] = fiv;
                // 출구 막힘
                if (map[ro[4]][panorder[i][4]][4][4] == 0) continue;

                for (int one = 0; one < 4; one++) {
                    ro[0] = one;
                    // 입구 막힘
                    if (map[ro[0]][panorder[i][0]][0][0] == 0) continue;

                    for (int two = 0; two < 4; two++) {
                        ro[1] = two;
                        for (int thr = 0; thr < 4; thr++) {
                            ro[2] = thr;
                            for (int fou = 0; fou < 4; fou++) {
                                ro[3] = fou;
                                bfs(i);
                                if (best == 12) {
                                    cout << best;
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << best;
}