Penerapan Struktur Graph Bipartite Pada Penyelesaian Persoalan E-Olymp 9006 Cross The River

Munawaroh, Siti (2022) Penerapan Struktur Graph Bipartite Pada Penyelesaian Persoalan E-Olymp 9006 Cross The River. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840007004-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Permasalahan pada tugas akhir ini adalah E-Olymp 9006 Cross The River. Dalam permasalahan ini diminta untuk mencari kemungkinan apakah terdapat solusi untuk menyebrangkan semua hewan yang ada di kebun binatang ke seberang sungai. Semua hewan harus dipindahkan ke seberang sungai hanya dengan menggunakan dua perahu saja. Di deskripsikan ada n hewan di kebun binatang tersebut jika dibiarkan bersama-sama tanpa adanya pengawasan maka salah satu dari mereka bisa memakan hewan lainnya. Untuk setiap hewan diketahui hewan apa saja yang bisa memakan hewan lainnya, dan pengawas ahli dalam mengatasi tersebut. Hewan apapun tidak bisa memakan hewan lainnya jika ada pengawas yang mengawasinya. Pengawas hanya memiliki dua perahu. Untuk alasan keamanan, perahu tidak bisa membawa lebih dari satu hewan ke dalam perahu. Di setiap perahu hanya bisa membawa satu hewan beserta pengawas. Pengawas bisa berenang menyebrangi sungai ke segala arah, tetapi perahu tidak bisa bergerak jika tanpa ada pengawas. Dan jika hewan dibiarkan tanpa pengawasan disatu sisi, hewan dapat saling memakan dam kecelakaan bisa terjadi. Tugas Akhir ini akan mengimplementasikan metode Graph Bipartite yang mengacu pada permasalahan penugasan mencari kemungkinan apakah terdapat solusi dalam menyebrangkan semua hewan. Dalam buku ini akan dibahas metode Graph Bipartite untuk menyelesaikan permasalahan Cross The River dengan menggunakan Bahasa Pemrograman
C++.Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan metode Graph Bipartite membutuhkn rata-rata waktu sebesar 17,6 detik dan rata-rata memori sebesar 792,8 Mib. Solusi ini berhasil menempati peringkat pertama pada situs E-Olymp Online Judge dan mendapatkan grade A+.
=================================================================================================================================
The problem in this final project is E-Olymp 9006 Cross The River. In this problem, they are asked to explore the possibility of whether there is a solution to cross all the animals in the zoo across the river. All animals must be moved across the river using only two boats. It is described that there are n animals in the zoo, if left together without supervision, one of them can eat other animals. For each animal it is known which animals can eat other animals, and supervisors are experts in dealing with these. Any animal cannot eat another animal if there is a supervisor watching over it. The supervisor only has two boats. For safety reasons, the boat cannot carry more than one animal on board. Each boat can only carry one animal along with a supervisor. The supervisor can swim across the river in any direction, but the boat cannot move without a supervisor. And if animals are left unattended on the one hand, animals can eat each other and accidents can occur. This final project will implement the Bipartite Graph method which refers to the assignment problem to find out whether there is a solution in crossing all animals. In this book, we will discuss the Bipartite Graph method to solve the Cross The River problem using the C++ Programming Language. of 792.8 Mib. This solution managed to rank first on the EOlymp Online Judge site and get an A+ grade.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Cross The River, Graph Bipartite.
Subjects:	T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	13 Oct 2025 06:04
Last Modified:	13 Oct 2025 06:04
URI:	http://repository.its.ac.id/id/eprint/128579

Actions (login required)

View Item