[BOJ] 16985. Maaaaaaaaaze - Graph/BF/BFS
Problem
제출일 : 2020-02-11
문제 풀이 시간 : 2H
난이도 : ★★★☆
link : https://www.acmicpc.net/problem/16985
평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.
대회의 규칙은 아래와 같다.
- 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.
- 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.
- 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.
- 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
- 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.
이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자.
input
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.
Output
첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.
Example
input
1 1 0 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
1 0 0 0 0
0 0 1 0 0
0 0 1 1 1
0 0 1 0 0
0 0 0 0 0
0 0 1 0 1
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 0 0
1 0 0 0 0
0 0 1 1 0
1 0 1 0 0
0 0 1 0 1
0 0 1 1 0
1 1 0 1 1
0 0 0 0 1
0 1 0 1 0
0 1 0 0 0
output
16
Solution & Inpression
위 문제는 $5 \times 5$의 판 $5$개가 주어진다.
각각의 판을 회전하고 층을 바꾸어 미로를 구성할 수 있다. 미로를 탈출할때 가장 적은 이동횟수를 출력하면 된다.
각각의 판의 층이 바뀌는 경우의 수는 $5!$ 이며 각 판은 $0,90,180,270$도씩 회전해 4개의 상태를 갖을수 있다,
따라서 생성가능한 미로의 수는
$$
5! \times 4^5 =75,000
$$
개의 미로를 생성할 수 있다
생성된 미로를 BFS로 탐색했다 3차원의 x,y,z축에서 각각 +1, -1로 한 칸씩 6방향으로 이동할 수 있다.
순열과 중복순열을 이용해 미로의 경우를 구했고 큐를 이용하여 너비우선 탐색을 구현했다.
Code
언어 : JAVA
메모리 : 279,664 kb
실행시간 : 1,176 ms
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[][][][] map = new int[5][4][5][5];
static int[] solData = new int[5], goData = new int[5];
static boolean[] visit = new boolean[5];
static int ans;
//상하좌우 아래 위
static int[] dx = { 0, 0, -1, 1, 0, 0 };
static int[] dy = { -1, 1, 0, 0, 0, 0 };
static int[] dz = { 0, 0, 0, 0, 1, -1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int k = 0; k < 5; k++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[k][0][i][j] = sc.nextInt();
}
}
rotateMap(k);
}
ans = Integer.MAX_VALUE;
solve(0); // 각 판의 회전 정도를 결정
if (ans == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(ans);
}
private static void solve(int depth) {
if (depth == 5) {
go(0); // 판의 순서를 결정
return;
}
for (int i = 0; i < 4; i++) {
solData[depth] = i;
solve(depth + 1);
}
}
private static void go(int depth) {
if (depth == 5) {
calc();
return;
}
for (int i = 0; i < 5; i++) {
if (!visit[i]) {
visit[i] = true;
goData[depth] = i;
go(depth + 1);
visit[i] = false;
}
}
}
private static void calc() {
int[][][] copy = new int[5][5][5];
for (int k = 0; k < 5; k++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
copy[k][i][j] = map[goData[k]][solData[k]][i][j];
}
}
}
// BFS
// 입구나 출구가 없는 경우
if (copy[0][0][0] != 1 || copy[4][4][4] != 1)
return;
Queue<int[]> q = new LinkedList<>();
boolean visit[][][] = new boolean[5][5][5];
q.offer(new int[] { 0, 0, 0, 0 });
visit[0][0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
// 최저값 보다 클 경우 종료
if (cur[3] >= ans)
return;
// 도착 종료
if (cur[0] == 4 && cur[1] == 4 && cur[2] == 4) {
if (ans > cur[3])
ans = cur[3];
return;
}
for (int dir = 0; dir < 6; dir++) {
int nz = cur[0] + dz[dir];
int ny = cur[1] + dy[dir];
int nx = cur[2] + dx[dir];
if (isRange(nz, ny, nx) && !visit[nz][ny][nx] && copy[nz][ny][nx] == 1) {
q.offer(new int[] { nz, ny, nx, cur[3] + 1 });
visit[nz][ny][nx] = true;
}
}
}
}
private static boolean isRange(int nz, int ny, int nx) {
if (0 <= nz && nz < 5 && 0 <= ny && ny < 5 && 0 <= nx && nx < 5)
return true;
return false;
}
private static void rotateMap(int k) {
for (int turn = 1; turn < 4; turn++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[k][turn][j][4 - i] = map[k][turn - 1][i][j];
}
}
}
}
}
