본문 바로가기

Programming/BOJ

BOJ 16985 · Maaaaaaaaaze


알고리즘 분류 : BFS, 브루트 포스  


3차원 미로를 탈출하는 것을 구현해야 한다. 단순한 3차원 BFS는, BOJ 7569번 '토마토'처럼 구현하면 된다. 하지만, 이 문제는 각 층의 미로가 회전하고, 각 층마다 섞여서 까다롭다. 미로를 제대로 만드는 것이 중요하다.


  • 미로 맵을 나타낼 3차원 배열의 인덱스는 [층 번호] [X좌표] [Y좌표] 이다.
  • 각 층을 섞는 것을 순열을 통해 만든다. 별도의 인덱스[0~4]를 만들어서 층을 나타내고, 이를 순열로 섞으면 된다.
  • 층을 섞은 후, 각 층을 회전해야 한다. 별도의 회전 함수를 만들고, 5중 for문 또는 재귀를 통해 각 층을 순차적으로 회전시킨다.
  • 첫 층의 출발 칸(0, 0, 0)이 이동할 수 있는 칸[1]인 경우에만 다음 층을 섞는다. 이동할 수 없는 칸[0]이라면 다음 층으로 이동할 수 없기 때문이다.
  • 층을 순서대로 회전시키면서 마지막 층까지 회전시킨 후, 도착 칸(4, 4, 4)이 이동할 수 있는 칸[1]인지 확인한다. 이동할 수 있는 칸이라면, BFS 탐색을 시작한다.
  • BFS 탐색을 할 때마다, 최단 거리 정보를 업데이트한다.
  • 만약 최단 거리가 12로 나왔다면, 이보다 더 짧을 수 없으므로, exit 함수를 통해 프로그램을 바로 종료한다. 이 부분을 처리하면 수행 시간을 대폭 줄일 수 있다.





C++ 소스코드


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;

struct maze {
    int x, y, z;
};

int a[5][5][5], b[5][5][5], d[5];
int dist[5][5][5], ans = 1e9;
const int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0 ,0, 0, 0, 1, -1};

void bfs() {
    queue<maze> q;
    q.push({0, 0, 0});
    memset(dist, -1, sizeof(dist));
    dist[0][0][0] = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = q.front().z; q.pop();
        if (x == 4 && y == 4 && z == 4) {
            ans = min(ans, dist[x][y][z]);
            if (ans == 12) {
                printf("12\n");
                exit(0);
            }
            return;
        }
        for (int i=0; i<6; i++) {
            int nx = x+dx[i], ny = y+dy[i], nz = z+dz[i];
            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || nz < 0 || nz >= 5) continue;
            if (b[nx][ny][nz] && dist[nx][ny][nz] == -1) {
                q.push({nx, ny, nz});
                dist[nx][ny][nz] = dist[x][y][z]+1;
            }
        }
    }
}

void rotate(int s) {
    int temp[5][5];
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            temp[j][4-i] = b[s][i][j];
        }
    }
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            b[s][i][j] = temp[i][j];
        }
    }
}

void solve() {
    do {
        for (int i=0; i<5; i++) {
            memcpy(b[d[i]], a[i], sizeof(a[i]));
        }
        for (int i=0; i<4; i++) {
            rotate(0);
            if (!b[0][0][0]) continue;
            for (int j=0; j<4; j++) {
                rotate(1);
                for (int k=0; k<4; k++) {
                    rotate(2);
                    for (int m=0; m<4; m++) {
                        rotate(3);
                        for (int n=0; n<4; n++) {
                            rotate(4);
                            if (b[4][4][4]) bfs();
                        }
                    }
                }
            }
        }
    } while (next_permutation(d, d+5));
}

int main() {
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            for (int k=0; k<5; k++) {
                scanf("%d", &a[i][j][k]);
            }
        }
    }
    for (int i=0; i<5; i++) d[i] = i;
    solve();
    printf("%d\n", ans == 1e9 ? -1 : ans);
    return 0;
}




Python 3 소스코드


from collections import deque
from itertools import permutations

ans = 10**9
dx, dy, dz = (1, -1, 0, 0, 0, 0), (0, 0, 1, -1, 0, 0), (0, 0, 0, 0, 1, -1)
a = [[list(map(int, input().split())) for _ in range(5)] for _ in range(5)]
b = [[[0]*5 for _ in range(5)] for _ in range(5)]

def bfs():
    global ans
    q = deque()
    q.append((0, 0, 0))
    dist = [[[-1]*5 for _ in range(5)] for _ in range(5)]
    dist[0][0][0] = 0
    while q:
        x, y, z = q.popleft()
        if (x, y, z) == (4, 4 ,4):
            ans = min(ans ,dist[x][y][z])
            if ans == 12:
                print(12)
                exit(0)
            return
        for i in range(6):
            nx, ny, nz = x+dx[i], y+dy[i], z+dz[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5 or nz < 0 or nz >= 5:
                continue
            if b[nx][ny][nz] and dist[nx][ny][nz] == -1:
                q.append((nx, ny, nz))
                dist[nx][ny][nz] = dist[x][y][z]+1

def rotate(k):
    temp = [[0]*5 for _ in range(5)]
    for i in range(5):
        for j in range(5):
            temp[j][4-i] = b[k][i][j]
    b[k] = temp

def maze(cnt):
    if cnt == 5:
        if b[4][4][4]:
            bfs()
        return
    for i in range(4):
        if b[0][0][0]:
            maze(cnt+1)
        rotate(cnt)

def solve():
    for d in permutations([0, 1, 2, 3, 4]):
        for i in range(5):
            b[d[i]] = a[i]
        maze(0)

solve()
print(ans if ans != 10**9 else -1)




참고



태그

  • 코딩초보 2020.03.09 21:16 댓글주소 수정/삭제 댓글쓰기

    궁금한게 있는데요 파이썬으로 구현하실 때, permutation 모듈을 통해 순열을 구성하여 bfs를 사용하는 것과 재귀를 통해 순열을 구성하고 bfs로 정답을 구하는 것의 속도 차이가 많이 나나요? 저는 후자의 방식을 사용했는데 시간초과가 더나더라구요 물론 백트래킹을 적용하였습니다.