Algorima DFS

 Di sebuah peta berbentuk persegi 5x5, terdapat seorang petualang yang memulai perjalanan dari titik awal yang ditandai dengan huruf S. Tujuan utamanya adalah mencapai titik G yang terletak di sudut lain dari peta.

Namun, perjalanan tidaklah mudah. Setiap langkah di peta memiliki biaya perjalanan. Angka yang tertera di setiap kotak adalah beban yang harus ditanggung oleh sang petualang ketika melangkah ke sana. Ada juga jalur berbahaya yang ditandai dengan angka 9, tempat terlarang yang tidak bisa dilewati sama sekali.

Sang petualang tidak bisa sembarangan berjalan. Ia hanya boleh bergerak ke atas, bawah, kiri, atau kanan, selangkah demi selangkah. Untuk menghindari kebingungan dan jebakan, ia menandai jalur yang sudah dikunjunginya agar tidak mengulanginya.

Dengan tekad yang kuat, ia menyusuri setiap kemungkinan jalan melalui DFS (Depth First Search)—sebuah strategi di mana ia berani masuk ke satu jalur hingga akhir, sebelum kembali dan mencoba jalur lain. Setiap kali mencapai Goal (G), ia mencatat total biaya perjalanan yang sudah ditempuh. Dari semua kemungkinan jalur yang ada, ia hanya akan memilih perjalanan dengan biaya minimum.

Akhirnya, setelah mencoba berbagai kemungkinan jalan, sang petualang menemukan jawaban: berapa biaya paling kecil untuk mencapai tujuan dari Start ke Goal. Itulah hasil yang ditampilkan di akhir program.

code

package com.example.belajar1;

import java.util.ArrayList;

public class PetaDFS {

    static char[][] peta = {

            {'S', '1', '1', '9', '1'},

            {'1', '2', '1', '1', '1'},

            {'1', '9', '2', '9', '1'},

            {'1', '1', '2', '1', '1'},

            {'1', '1', '1', '2', 'G'}

    };

    static int min = Integer.MAX_VALUE;

    static boolean[][] kunjungi = new boolean[5][5];

    public static void main(String[] args) {

        dfs(0, 0, 0);

        System.out.println("Biaya minimum: " + min);

    }

    private static void dfs(int i, int j, int biaya) {

        if (i < 0 || i >= 5 || j < 0 || j >= 5 || peta[i][j] == '9' || kunjungi[i][j]) return;

        if (peta[i][j] == 'G') {

            min = Math.min(min, biaya);

            return;

        }

        int nilai = (peta[i][j] == 'S') ? 0 : (peta[i][j] - '0');

        kunjungi[i][j] = true;

        dfs(i + 1, j, biaya + nilai); // bawah

        dfs(i - 1, j, biaya + nilai); // atas

        dfs(i, j + 1, biaya + nilai); // kanan

        dfs(i, j - 1, biaya + nilai); // kiri

        kunjungi[i][j] = false;

    }

}

Output