[백준] 16985번 Maaaaaaaaaze C++

개발/알고리즘 & PS 2023. 10. 19. 22:21

https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을

www.acmicpc.net

3차원 BFS에 층별 재배치, 회전까지 들어가 있는 문제이다. 단순하게 모든 경우의 수에 BFS를 해보면 된다. 구현이 살짝 많다.

풀이 구상

층별 배열 순서를 결정한다.
각 층을 회전시킨다.
BFS를 수행하고 최단거리를 구한다.

permutation → 백트래킹 → BFS 순으로 알고리즘을 사용했다.

next_permutation

각 층을 배열하는 경우의 수를 모두 구하려면 algorithm 헤더의 next_permutation을 활용할 수 있다.

int perm[] = { 1, 1, 0, 0, 0 };  
int data[] = { 1, 2, 3, 4, 5 };  

sort(perm, perm + 5);  

do {  
    for (int i = 0; i < 5; i++) {  
        if (perm[i] == 1)  
        cout << data[i] << ' ';  
    }

    cout << '\n';
} while (next_permutation(perm, perm + 5));

위 코드는 1~5 중 2개의 숫자를 뽑는 경우를 모두 나열하는 코드이다. next_permutation에 사용되는 배열 perm은 오름차순 정렬되어 있어야 모든 경우의 수를 구할 수 있다. 위 코드에선 1, 1, 0, 0, 0을 나열하는 모든 경우의 수를 구하고 1인 부분만 선택해 출력한다. 이번 문제에서는 5개 전부 나열해야 하니 permutation의 결과를 그대로 쓰면 된다.

2차원 배열 회전

각 층을 회전시키려면 여러 방법이 있지만, 2차원 배열인 층 하나를 통째로 돌릴 수 있다. 이 경우 BFS가 굉장히 직관적이게 된다는 장점이 있다. 대신 추가적인 연산이 발생하지만 5*5 배열이므로 크게 문제 되진 않는다.

N * N 배열을 오른쪽으로 90도 회전하는 코드는 아래와 같다.

int temp[N][N];

for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
        temp[i][j] = arr[N - j -1][i];

memmove(arr, temp, sizeof(arr));

cstring헤더의 memmove를 이용하면 2차원 배열을 복사할 수 있다.

층 회전하기

백트레킹을 이용해 층을 회전한다. 이번 경우 첫 번째 층은 회전시키지 않고 첫 층의 네 꼭짓점 모두에서 시작한다.

코드 설명

#define INF 1000000000

int original[5][5][5];
int graph[5][5][5];
int mind = INF;
int dx[] = { -1, 1, 0, 0, 0, 0 };
int dy[] = { 0, 0, -1, 1, 0, 0 };
int dz[] = { 0, 0, 0, 0, -1, 1 };
int sec[5];
bool visited[5][5][5];

최단거리를 위해 1e9를 INF로 정의한다. sec은 각 층의 순서이다. seq으로 했어야 했는데 오타이다 ㅎㅎ; 최단거리를 graph를 오염시키는 방식으로 계산했기 때문에 원본 데이터를 따로 저장해 계속 리셋해 줬다. 최단 거리를 mind(min distance)에 저장한다.

int perm[] = { 0, 1, 2, 3, 4 };
do {
    for (int i = 0; i < 5; i++)
        sec[perm[i]] = i;

    backtrackRotation(0);
} while (next_permutation(perm, perm + 5));

permutation을 통해 각 층의 순서를 결정한다. 순서를 모두 지정한 후 백트래킹으로 회전을 수행한다.

void backtrackRotation(int d) {
    if (d == 4) {
        bfs();
        return;
    }

    for (int i = 0; i < 4; i++) {
        backtrackRotation(d + 1);
        rotate(d + 1);
    }
}

각 층이 회전하는 경우를 백트래킹으로 탐색한다. 회전이 완료되면 bfs를 통해 최단거리를 업데이트한다.

void rotate(int n) {
    int temp[5][5];

    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            temp[i][j] = original[sec[n]][4 - j][i];

    memmove(original[sec[n]], temp, sizeof(original[sec[n]]));
}

n번째 층을 오른쪽으로 90도 회전한다.

void bfs() {
    for (int e = 0; e < 4; e++) {
        queue<tuple<int, int, int>> q;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                fill(visited[i][j], visited[i][j] + 5, false);
        for (int i = 0; i < 5; i++)
            memmove(graph[i], original[i], sizeof(graph[i]));

        int x0 = 0;
        int y0;
        int z0;
        if (e == 0 && graph[sec[0]][0][0] == 1) {
            q.emplace(0, 0, 0);
            y0 = 0;
            z0 = 0;
            visited[0][0][0] = true;
        } else if (e == 1 && graph[sec[0]][4][0] == 1) {
            q.emplace(0, 4, 0);
            y0 = 4;
            z0 = 0;
            visited[0][4][0] = true;
        } else if (e == 2 && graph[sec[0]][0][4] == 1) {
            q.emplace(0, 0, 4);
            y0 = 0;
            z0 = 4;
            visited[0][0][4] = true;
        } else if (e == 3 && graph[sec[0]][4][4] == 1) {
            q.emplace(0, 4, 4);
            y0 = 4;
            z0 = 4;
            visited[0][4][4] = true;
        }

        bool done = false;
        while (!done && !q.empty()) {
            int x, y, z;
            tie(x, y, z) = q.front();
            q.pop();
            int dist = graph[sec[x]][y][z] + 1;

            for (int i = 0; i < 6; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nz = z + dz[i];

                if (
                    nx < 0 || ny < 0 || nz < 0 ||
                    nx >= 5 || ny >= 5 || nz >= 5 ||
                    graph[sec[nx]][ny][nz] == 0 ||
                    visited[nx][ny][nz]
                )
                    continue;

                if ((nx == 0 || nx == 4) && (ny == 0 || ny == 4) && (nz == 0 || nz == 4)) {
                    int sameCnt = 0;
                    if (nx == x0)
                        sameCnt++;
                    if (ny == y0)
                        sameCnt++;
                    if (nz == z0)
                        sameCnt++;

                    if (sameCnt == 0) {
                        if (dist < mind)
                            mind = dist;

                        done = true;
                        break;
                    }
                }

                visited[nx][ny][nz] = true;
                graph[sec[nx]][ny][nz] = dist;
                q.emplace(nx, ny, nz);
            }
        }
    }
}

첫 층의 4 꼭짓점에서 시작해 BFS를 수행한다. graph와 visited를 리셋하고 시작해야 한다. 처음에 문제를 잘못 읽고 출구까지 도착했는지 검사하는 코드가 깔끔하지 않았다.

전체 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <queue>

using namespace std;

#define INF 1000000000

int original[5][5][5];
int graph[5][5][5];
int mind = INF;
int dx[] = { -1, 1, 0, 0, 0, 0 };
int dy[] = { 0, 0, -1, 1, 0, 0 };
int dz[] = { 0, 0, 0, 0, -1, 1 };
int sec[5];
bool visited[5][5][5];

void bfs() {
    for (int e = 0; e < 4; e++) {
        queue<tuple<int, int, int>> q;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                fill(visited[i][j], visited[i][j] + 5, false);
        for (int i = 0; i < 5; i++)
            memmove(graph[i], original[i], sizeof(graph[i]));

        int x0 = 0;
        int y0;
        int z0;
        if (e == 0 && graph[sec[0]][0][0] == 1) {
            q.emplace(0, 0, 0);
            y0 = 0;
            z0 = 0;
            visited[0][0][0] = true;
        } else if (e == 1 && graph[sec[0]][4][0] == 1) {
            q.emplace(0, 4, 0);
            y0 = 4;
            z0 = 0;
            visited[0][4][0] = true;
        } else if (e == 2 && graph[sec[0]][0][4] == 1) {
            q.emplace(0, 0, 4);
            y0 = 0;
            z0 = 4;
            visited[0][0][4] = true;
        } else if (e == 3 && graph[sec[0]][4][4] == 1) {
            q.emplace(0, 4, 4);
            y0 = 4;
            z0 = 4;
            visited[0][4][4] = true;
        }

        bool done = false;
        while (!done && !q.empty()) {
            int x, y, z;
            tie(x, y, z) = q.front();
            q.pop();
            int dist = graph[sec[x]][y][z] + 1;

            for (int i = 0; i < 6; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nz = z + dz[i];

                if (
                    nx < 0 || ny < 0 || nz < 0 ||
                    nx >= 5 || ny >= 5 || nz >= 5 ||
                    graph[sec[nx]][ny][nz] == 0 ||
                    visited[nx][ny][nz]
                )
                    continue;

                if ((nx == 0 || nx == 4) && (ny == 0 || ny == 4) && (nz == 0 || nz == 4)) {
                    int sameCnt = 0;
                    if (nx == x0)
                        sameCnt++;
                    if (ny == y0)
                        sameCnt++;
                    if (nz == z0)
                        sameCnt++;

                    if (sameCnt == 0) {
                        if (dist < mind)
                            mind = dist;

                        done = true;
                        break;
                    }
                }

                visited[nx][ny][nz] = true;
                graph[sec[nx]][ny][nz] = dist;
                q.emplace(nx, ny, nz);
            }
        }
    }
}

void rotate(int n) {
    int temp[5][5];

    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            temp[i][j] = original[sec[n]][4 - j][i];

    memmove(original[sec[n]], temp, sizeof(original[sec[n]]));
}

void backtrackRotation(int d) {
    if (d == 4) {
        bfs();
        return;
    }

    for (int i = 0; i < 4; i++) {
        backtrackRotation(d + 1);
        rotate(d + 1);
    }
}

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

    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 5; k++)
                cin >> original[i][j][k];

    int perm[] = { 0, 1, 2, 3, 4 };
    do {
        for (int i = 0; i < 5; i++)
            sec[perm[i]] = i;

        backtrackRotation(0);
    } while (next_permutation(perm, perm + 5));

    if (mind == INF)
        cout << -1;
    else
        cout << mind - 1;
}

저작자표시

'개발 > 알고리즘 & PS' 카테고리의 다른 글

[BOJ] 11508 2+1 세일 - C++ (0)	2024.04.01
[BOJ] 20153 영웅이는 2의 거듭 제곱을 좋아해! - C++ (0)	2024.03.29
[BOJ] 14606 피자 (Small) - C++ (0)	2024.03.29
[BOJ] 17532 여러분의 다리가 되어 드리겠습니다! - C++ (0)	2024.01.13
[백준] 1062 가르침 C++ (2)	2023.10.18

ABOUT ME

YEAHx4 Dev YEAHx4 Dev

풀이 구상

next_permutation

2차원 배열 회전

층 회전하기

코드 설명

전체 코드

'개발 > 알고리즘 & PS' 카테고리의 다른 글

티스토리툴바

ABOUT ME

풀이 구상

next_permutation

2차원 배열 회전

층 회전하기

코드 설명

전체 코드

'개발 > 알고리즘 & PS' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바