TUGAS 4 MK ALGORITMA

 BFS

Di sebuah pusat penelitian, ada drone pintar yang harus menavigasi sebuah ruang simulasi berbentuk grid 5x5. Drone ini harus berangkat dari titik S di pojok kiri atas (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