평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.
대회의 규칙은 아래와 같다.
참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.
이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자.
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.
첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
12
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
-1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
12
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
12
0 0 0 1 0
0 0 0 0 0
1 0 1 1 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 1 0 0 0
1 0 0 1 0
0 1 1 1 0
0 1 0 1 0
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
1 0 0 0 1
1 0 0 0 0
0 0 1 0 1
0 1 1 0 0
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 0 0 0
22
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 0 1 0
0 1 1 0 0
0 1 0 0 0
1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
1 0 0 1 1
1 0 0 0 0
-1
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
16
이 문제는 DFS 알고리즘을 통해 순열로 층의 순서를 정한 뒤에 가능한 모든 경우의 수를 구한 뒤 BFS 알고리즘을 이용해 최단 거리를 구할 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int[][][] map = new int[5][5][5];
static int[][][] origin = new int[5][5][5];
static int[] dx = {-1, 1, 0, 0, 0, 0};
static int[] dy = {0, 0, -1, 1, 0, 0};
static int[] dz = {0, 0, 0, 0, -1, 1};
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
String[] input = br.readLine().split(" ");
for(int k=0; k<5; k++) {
origin[i][j][k] = Integer.parseInt(input[k]);
}
}
}
ArrayList<Integer> list = new ArrayList<>();
boolean[] visited = new boolean[5];
perm(visited, list);
if(min==Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(min);
}
public static void perm(boolean[] visited, ArrayList<Integer> list) {
if(list.size()==5) {
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
for(int k=0; k<5; k++) {
map[i][j][k] = origin[list.get(i)][j][k];
}
}
}
if(min!=12)
sol();
return;
}
for(int i=0; i<5; i++) {
if(!visited[i]) {
visited[i] = true;
list.add(i);
perm(visited, list);
visited[i] = false;
list.remove(list.size()-1);
}
}
}
public static int bfs() {
Queue<Pair> queue = new LinkedList<>();
boolean[][][] visited = new boolean[5][5][5];
int cnt = Integer.MAX_VALUE;
visited[0][0][0] = true;
queue.add(new Pair(0, 0, 0, 0));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.x==4 && temp.y==4 && temp.z==4) {
cnt = temp.cnt;
break;
}
for(int i=0; i<6; i++) {
int nx = temp.x + dx[i];
int ny = temp.y + dy[i];
int nz = temp.z + dz[i];
if(nx<0 || nx>=5 || ny<0 || ny>=5 || nz<0 || nz>=5 || visited[nz][nx][ny] || map[nz][nx][ny]==0) continue;
visited[nz][nx][ny] = true;
queue.add(new Pair(nx, ny, nz, temp.cnt+1));
}
}
return cnt;
}
public static void sol() {
if (map[0][0][0] == 1 && map[4][4][4] == 1) {
int dist = bfs();
min = Math.min(min, dist);
}
for (int a = 0; a < 4; a++) {
rotate(0);
for (int b = 0; b < 4; b++) {
rotate(1);
for (int c = 0; c < 4; c++) {
rotate(2);
for (int d = 0; d < 4; d++) {
rotate(3);
for (int e = 0; e < 4; e++) {
rotate(4);
if (map[0][0][0] == 1 && map[4][4][4] == 1) {
int dist = bfs();
min = Math.min(min, dist);
}
}
}
}
}
}
}
public static void rotate(int z) {
int[][] temp = new int[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
temp[j][4 - i] = map[z][i][j];
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[z][i][j] = temp[i][j];
}
}
}
public static class Pair {
int x;
int y;
int z;
int cnt;
public Pair(int x, int y, int z, int cnt) {
this.x = x;
this.y = y;
this.z = z;
this.cnt = cnt;
}
}
}