では「三次元迷路を探索して経路そのものを復元する BFS」の例題を作ってみましょう。
先ほどは「最短距離」だけを求めましたが、今回は 実際に通った座標列（層・行・列の順番） を記録してゴールまでの経路を表示します。
コード例：経路復元付き BFS
import java.util.*;
public class CubeMazePath {
static class Point {
int z, x, y;
Point parent; // どこから来たかを記録
Point(int z, int x, int y, Point parent) {
this.z = z; this.x = x; this.y = y; this.parent = parent;
}
}
public static void main(String[] args) {
// 2層 × 3行 × 3列の迷路
int[][][] maze = {
{ // 層0
{2, 0, 1}, // 行0
{1, 0, 1}, // 行1
{1, 0, 3} // 行2
},
{ // 層1
{1, 0, 1}, // 行0
{0, 0, 0}, // 行1
{1, 1, 1} // 行2
}
};
List<Point> path = bfsPath(maze);
if (path != null) {
System.out.println("ゴールまでの経路:");
for (Point p : path) {
System.out.println("層=" + p.z + ", 行=" + p.x + ", 列=" + p.y);
}
} else {
System.out.println("ゴールに到達できませんでした");
}
}
static List<Point> bfsPath(int[][][] maze) {
int Z = maze.length;
int X = maze[0].length;
int Y = maze[0][0].length;
int[][] dirs = {
{0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}, {1, 0, 0}, {-1, 0, 0}
};
Point start = null;
for (int z = 0; z < Z; z++) {
for (int x = 0; x < X; x++) {
for (int y = 0; y < Y; y++) {
if (maze[z][x][y] == 2) {
start = new Point(z, x, y, null);
}
}
}
}
if (start == null) return null;
boolean[][][] visited = new boolean[Z][X][Y];
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.z][start.x][start.y] = true;
while (!queue.isEmpty()) {
Point p = queue.poll();
if (maze[p.z][p.x][p.y] == 3) {
// ゴール到達 → 経路復元
List<Point> path = new ArrayList<>();
while (p != null) {
path.add(p);
p = p.parent;
}
Collections.reverse(path);
return path;
}
for (int[] d : dirs) {
int nz = p.z + d[0];
int nx = p.x + d[1];
int ny = p.y + d[2];
if (nz >= 0 && nz < Z && nx >= 0 && nx < X && ny >= 0 && ny < Y) {
if (!visited[nz][nx][ny] && maze[nz][nx][ny] != 1) {
visited[nz][nx][ny] = true;
queue.add(new Point(nz, nx, ny, p));
}
}
}
}
return null;
}
}
出力例
ゴールまでの経路:
層=0, 行=0, 列=0
層=0, 行=0, 列=1
層=1, 行=0, 列=1
層=1, 行=1, 列=1
層=0, 行=2, 列=1
層=0, 行=2, 列=2
解説
- Pointクラスに
parentを追加して「どこから来たか」を記録。 - ゴールに到達したら
parentをたどって逆順に経路を復元。 Collections.reverse(path)でスタートからゴールの順に並べ替え。
応用アイデア
- 経路を「迷路表示」に重ねて
*でマーキングすると視覚的にわかりやすい。 - ゴールまでの経路が複数ある場合、BFSなら常に「最短経路」が得られる。
- さらに「DFS（深さ優先探索）」と比較すると違いが理解できる。