BFS
(0,0) dan mencapai titik G di pojok kanan bawah (4,4) untuk menyelesaikan misinya.Dalam ruang simulasi:
Angka 1 berarti jalur biasa, drone menghabiskan energi kecil untuk melewatinya.
Angka 2 berarti jalur lebih berat, drone perlu mengeluarkan energi ekstra.
Angka 9 berarti ada rintangan besar seperti dinding, drone tidak bisa melewatinya.
Drone tidak asal memilih jalan. Ia menggunakan algoritma BFS (Breadth-First Search), yang membuatnya selalu menyebar ke semua arah yang mungkin secara bertahap. Dengan cara ini, drone bisa memastikan menemukan jalan keluar menuju G.
Perjalanan drone:
Dari S(0,0), drone mencoba dua arah: ke kanan (0,1) dan ke bawah (1,0). Keduanya bisa dilewati dengan energi 1 sehingga masuk daftar eksplorasi.
Dari (0,1), drone melanjutkan ke kanan (0,2) dengan energi 1`.
Dari (1,0), drone bisa turun ke (2,0) dengan energi 1`.
Dari (0,2), ke kanan (0,3) tidak bisa karena ada rintangan, tapi ke bawah (1,2) bisa dilewati.
Dari (2,0), drone turun lagi ke (3,0) dengan energi 1`.
Dari (1,2), drone ke kanan (1,3) dan masuk jalur aman.
Dari (3,0), drone turun ke (4,0) dengan energi 1`.
Dari (4,0), drone ke kanan (4,1) dengan energi 1`.
Dari (4,1), drone melanjutkan ke (4,2) dengan energi 1`.
Dari (4,2), drone ke kanan (4,3) dengan energi 2`.
Dari (4,3), drone akhirnya menuju G(4,4) dan sampai di titik tujuan.
import java.util.*;
public class bfs {
static int ROWS = 5, COLS = 5;
static int[][] grid = {
{0,1,1,9,1},
{1,2,1,1,1},
{1,9,2,9,1},
{1,1,2,1,1},
{1,1,1,2,0}
};
static int[] start = {0,0};
static int[] goal = {4,4};
static int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
static class Node {
int r, c;
Node parent;
Node(int r, int c, Node parent) {
this.r = r;
this.c = c;
this.parent = parent;
}
}
public static void main(String[] args) {
bfs();
}
static void bfs() {
boolean[][] visited = new boolean[ROWS][COLS];
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(start[0], start[1], null));
visited[start[0]][start[1]] = true;
Node endNode = null;
while(!queue.isEmpty()) {
Node current = queue.poll();
if(current.r == goal[0] && current.c == goal[1]) {
endNode = current;
break;
}
for(int[] d : directions) {
int nr = current.r + d[0];
int nc = current.c + d[1];
if(nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS && !visited[nr][nc]) {
if(grid[nr][nc] != 9) {
visited[nr][nc] = true;
queue.add(new Node(nr, nc, current));
}
}
}
}
if(endNode != null) {
printPath(endNode);
} else {
System.out.println("Tidak ada jalur dari S ke G!");
}
}
static void printPath(Node endNode) {
List<int[]> path = new ArrayList<>();
Node current = endNode;
int totalCost = 0;
while(current != null) {
path.add(new int[]{current.r, current.c});
if(!(current.r == start[0] && current.c == start[1]) &&
!(current.r == goal[0] && current.c == goal[1])) {
totalCost += grid[current.r][current.c];
}
current = current.parent;
}
Collections.reverse(path);
System.out.print("Jalur yang paling pendek ");
for(int[] p : path) {
System.out.print("(" + p[0] + "," + p[1] + ")");
}
System.out.println(" Total biaya: " + totalCost);
}
}
outputnya:
alur yang paling pendek (0,0)(1,0)(2,0)(3,0)(4,0)(4,1)(4,2)(4,3)(4,4) Total biaya: 8
