16985. Maaaaaaaaaze

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

16985번: Maaaaaaaaaze

 

풀이

문제를 풀기 위해서는 가능한 3차원 미로를 모두 만들어 보기 위한 백트래킹, 최단경로를 찾기 위한 BFS 알고리즘을 사용하는 것이 요구된다.

 

구현 과정은 다음과 같다.

1. 미로 정보를 받아 변수에 저장한다. 이 변수가 가능한 모든 3차원 미로를 만들기 위한 원본이 된다.
2. 출력할 값인 최단거리를 저장하는 변수를 적당히 큰 값으로 초기화한다. 미로의 크기는 5 × 5 × 5 = 125이므로 125를 넘는 정도의 값으로 초기화하면 충분하다.
3. 원본에서 미로의 층수를 서로 바꾸거나, 특정 층을 회전시키는 변형을 가해서 새로운 3차원 미로를 만든다. 이 미로가 BFS를 실행할 미로가 된다.
4. 만든 미로의 입구나 출구가 막혀 있지 않은지 확인한다.
5. 막혀 있지 않다면 BFS를 실행하여 최단 이동 횟수를 구한다.
6. 구한 최단 이동 횟수를 2에서 초기화한 변수값과 비교하여 더 작은 값을 저장한다.
7. 가능한 모든 3차원 미로에 대하여 3~6을 반복한다.
8. 최단 이동 횟수가 저장된 변수의 값을 출력한다. 이때, 변수의 값이 2에서 초기화한 값 그대로라면 모든 3차원 미로가 탈출 불가능하단 뜻이므로 -1을 대신 출력한다.

 

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <tuple>
#define IN    order[0]
#define OUT   order[4]
using namespace std;

int maze[5][5][5];		// 미로 원본
int created[5][5][5];	// maze 변수를 바탕으로 재구성한 미로
int checked[5][5][5];
int order[] = {0, 1, 2, 3, 4};
int dx[] = {1, 0, 0, -1, 0, 0};
int dy[] = {0, 1, 0, 0, -1, 0};
int dz[] = {0, 0, 1, 0, 0, -1};
int ans = 200;

// 한 층의 미로를 회전시키는 함수
void rotate(int n, int id) {
    switch(id) {
        case 0:
            for(int i = 0; i < 5; i++) {
                for(int j = 0; j < 5; j++) {
                    created[n][i][j] = maze[n][4 - j][i];
                }
            }
            break;
        case 1:
            for(int i = 0; i < 5; i++) {
                for(int j = 0; j < 5; j++) {
                    created[n][i][j] = maze[n][4 - i][4 - j];
                }
            }
            break;
        case 2:
            for(int i = 0; i < 5; i++) {
                for(int j = 0; j < 5; j++) {
                    created[n][i][j] = maze[n][j][4 - i];
                }
            }
            break;
        case 3:
            memcpy(created[n], maze[n], sizeof(maze[n]));
            break;
    }
}

// BFS 실행 함수
void bfs() {
    queue<tuple<int, int, int>> q;
    checked[0][0][0] = 0;
    q.emplace(0, 0, 0);
    
    while(!q.empty()) {
        int curz, curx, cury;
        tie(curz, curx, cury) = q.front();
        q.pop();
        
        if(checked[4][4][4] != -1) {
            ans = min(ans, checked[4][4][4]);
            break;
        }
        
        for(int i = 0; i < 6; i++) {
            int nz = curz + dz[i];
            int nx = curx + dx[i];
            int ny = cury + dy[i];
            
            if(nz < 0 || nz >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            if(created[order[nz]][nx][ny] == 0 || checked[nz][nx][ny] != -1) continue;
            
            checked[nz][nx][ny] = checked[curz][curx][cury] + 1;
            q.emplace(nz, nx, ny);
        }
    }
    
    memset(checked, -1, sizeof(checked));
}

// 원본 미로에서 특정한 층을 회전시키는 변형을 가해 새 미로를 만드는 함수
void createMaze(int cnt) {
    if(ans == 12) return;	// 최단거리가 12일 경우 탐색 중단
    if(cnt >= 5) {
        if(created[IN][0][0] && created[OUT][4][4]) bfs();
        return;
    }
    
    for(int i = 0; i < 4; i++) {
        createMaze(cnt + 1);
        rotate(order[cnt], i);
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                cin >> maze[i][j][k];
                created[i][j][k] = maze[i][j][k];
            }
        }
    }
    
    memset(checked, -1, sizeof(checked));
    
    do {
        createMaze(0);
    } while(next_permutation(order, order + 5) && ans != 12);	// 최단거리가 12일 경우 탐색 중단
    
    if(ans == 200) cout << -1;
    else cout << ans;
    return 0;
}

실행 시간: 12 ms

사용 메모리: 2028 KB

 

미로의 원본 정보는 3차원 배열 maze에 저장하였고, 이 정보를 변형하여 BFS를 실행할 미로가 저장된 배열 created에 저장하였다. 이때, 각 2차원 미로의 층 위치는 3차원 배열의 값을 직접 변경하지 않고도 바꿀 수 있다. 필자는 배열 order에 미로의 층 순서를 저장하고, 이 값을 next_permutation 함수로 바꾸기만 함으로써 미로의 층이 바뀐 효과를 낼 수 있었다.

 

또한 문제 그대로 코드를 작성하여 구현하면 실행 시간이 300~400 ms대가 나오는데, 이를 최적화할 수 있는 팁이 있다. 주어진 미로의 크기는 5 × 5 × 5로 고정되어 있으므로, 해당 미로의 최단 이동 횟수는 12에서 더 줄어들지 않음을 알 수 있다. 따라서 BFS 실행 후 최단 이동 횟수가 12로 나온다면 더 이상의 탐색은 무의미하므로 바로 탐색을 중단하고 결과값을 출력할 수 있다. 실제로 이를 적용한 결과, 함수 호출이 획기적으로 줄어들어 12 ms의 실행 시간을 확보할 수 있었다.