Ada dua permasalahan yang harus diselesaikan di soal ini:
Apakah terdapat jalan yang valid antara point A (Acep) dan point B (Venue)?
Bila iya, rute apa yang harus Acep ambil?
Ada dua cara untuk menyelesaikan soal semacam ini, yaitu dengan menggunakan DFS atau BFS.
Depth First Search (DFS)
Depth First Search (DFS) adalah algoritma yang digunakan untuk menelusuri sebuah graph dari sebuah titik awal. Dari sebuah titik awal, algoritma ini akan memilih sebuah langkah dan mencoba menelusuri graph sejauh mungkin sebelum “kembali” dan mencoba langkah lain. Karena kita tidak peduli apakah langkah yang diambil adalah langkah terpendek atau bukan, kita dapat menggunakan DFS untuk mencari rute dari Acep ke Venue.
Untuk menyelesaikan permasalahan (1), solusi DFS yang perlu dibuat cukup sederhana.
Tetapi kode itu tidak cukup untuk menyelesaikan soal ini. Bagaimana cara untuk mengetahui rute yg diambil dari kode diatas? Salah satu caranya yaitu dengan menyimpan rute sebagai argument.
Solusi di atas akan mendapatkan verdict Accepted. Namun, kita dapat mengoptimasi algoritma tersebut supaya tidak terus menerus meng-copy path pada setiap pemanggilan fungsi dfs. Cara di atas dapat memakan memori yang lebih dari yang seharusnya.
Kita dapat menggunakan sebuah variable global untuk menyimpan path yang kita cari seperti berikut.
Kompleksitas waktu dan memori dari kode di atas adalah setara dengan jumlah node pada graf, karena tiap node hanya dikunjungi sekali. Dalam hal ini, kompleksitasnya adalah $O(N^2)$.
Breadth First Search (BFS)
Solusi BFS diserahkan kepada pembaca sebagai latihan.