Olimpiade Komputer SMA Tingkat Kabupaten
- OSK 2006 - Download -
- OSK 2007 - Download -
- OSK 2008 - Download - OSK 2009 - Download -
- OSK 2010 - Download -
- OSK 2011 - Download -
- OSK 2012 - Download -
- OSK 2013 - Download - [Pembahasan]
- OSK 2014 - Download - [Beserta Kunci Jawaban]
Olimpiade Komputer SMA Tingkat Provinsi
- OSP 2006 - Download -
- OSP 2007 - Download -
- OSP 2008 - Download -
- OSP 2009 - Download -
- OSP 2010 - Download -
- OSP 2011 - Download - [Pembahasan]
- OSP 2012 - Download - [Pembahasan]
- OSP 2013 - Download -
Olimpiade Komputer SMA Tingkat Nasional
- OSN 2006 - Download -
- OSN 2007 - Download -
- OSN 2008 - Download -
- OSN 2009 - Download -
- OSN 2010 - Download -
- OSN 2011 - Download -
- OSN 2012 - Download -
- OSN 2013 - Download -
22
Pak Dengklek ingin mengikuti kursus berternak bebek unggul. Kursus tersebut terdiri dari modul C1 s.d. C12, dan setiap modul membutuhkan 3 bulan. Urutan modul ditunjukkan pada graf sebagai berikut, dimana arah panah: C1-C2 berarti pak dengklek harus lulus C1 sebelum mengikuti C2. Pak Dengklek harus lulus C4 dan C13 sebelum mengikuti C14. Beberapa modul boleh diikuti secara paralel, pak Dengklek dapat melakukan sekaligus karena beliau sangat pandai.
Jika setiap modul membutuhkan 3 bulan, berapa lama minimum pak Dengklek dapat menyelesaikan kursusnya?
a. 9
b. 15
c. 21
d. 30
e. 42
Solusi : Breadth First Search (BFS)
Algoritma :
1. Buat sebuah antrian yang memuat nama kursus
2. Masukkan kursus yang harus diikuti pertama kali (kursus ini akan ditandai sebagai kursus yang sudah diikuti)
3. Untuk setiap kursus B yang dapat diikuti setelah menyelesaikan suatu kursus A dan kursus B tersebut belum diikuti, buang kursus A, masukkan kursus B ke dalam antrian
4. Tandai kursus B tadi sebagai kursus yang telah diikuti
5. Jika semua kursus sudah diikuti alias antriannya sudah kosong, berhenti. Jika antrian belum kosong, ulangi langkah ke-3
Waktu = 0 bulan, jika antrian terisi, waktu akan bertambah 3 bulan
Antrian : [ ] (kosong)
Kursus yang bisa diikuti Pak Dengklek adalah C1 dan C13
Antrian : [C1, C13], waktu = 3 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C1 => C2, C3, C4
Buang C1 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C13 => C4, C14
Buang C13 dalam antrian
Antrian : [ ]
Masukkan C2, C3, C4, C14 dalam antrian
Antrian : [C2, C3, C4, C14], waktu = 6 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C2 => C3
Karena C3 sudah dipelajari, maka tidak usah dimasukkan
Buang C2 dari antrian
- Kursus yang dapat diikuti setelah menyelesaikan C3 => C6, C7, C9, C10
Buang C3 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C4 => C14
Karena C14 sudah dipelajari, maka tidak usah dimasukkan
Buang C4 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C14 => C5
Buang C14 dalam antrian
Antrian : [ ]
Masukkan C5, C6, C7, C9, C10 ke dalam antrian
Antrian : [C5, C6, C7, C9, C10], waktu = 9 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C5 => C8
Buang C5 dari antrian
- Kursus yang dapat diikuti setelah menyelesaikan C6 => tidak ada
Buang C6 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C7 => tidak ada
Buang C7 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C9 => tidak ada
Buang C9 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C10 => C11
Buang C10 dalam antrian
Antrian : [ ]
Masukkan C8, C11 ke dalam antrian
Antrian : [C8, C11], waktu = 12 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C8 => tidak ada
Buang C8 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C11 => C12
Buang C11 dalam antrian
Antrian : [ ]
Masukkan C12 dalam antrian
Antrian : [C12], waktu = 15 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C12 => tidak ada
Buang C12 dalam antrian
Antrian : [ ]
Semua kursus sudah diikuti dan algoritma berhenti
Jawab : 15 bulan
1. Buat sebuah antrian yang memuat nama kursus
2. Masukkan kursus yang harus diikuti pertama kali (kursus ini akan ditandai sebagai kursus yang sudah diikuti)
3. Untuk setiap kursus B yang dapat diikuti setelah menyelesaikan suatu kursus A dan kursus B tersebut belum diikuti, buang kursus A, masukkan kursus B ke dalam antrian
4. Tandai kursus B tadi sebagai kursus yang telah diikuti
5. Jika semua kursus sudah diikuti alias antriannya sudah kosong, berhenti. Jika antrian belum kosong, ulangi langkah ke-3
Waktu = 0 bulan, jika antrian terisi, waktu akan bertambah 3 bulan
Antrian : [ ] (kosong)
Kursus yang bisa diikuti Pak Dengklek adalah C1 dan C13
Antrian : [C1, C13], waktu = 3 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C1 => C2, C3, C4
Buang C1 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C13 => C4, C14
Buang C13 dalam antrian
Antrian : [ ]
Masukkan C2, C3, C4, C14 dalam antrian
Antrian : [C2, C3, C4, C14], waktu = 6 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C2 => C3
Karena C3 sudah dipelajari, maka tidak usah dimasukkan
Buang C2 dari antrian
- Kursus yang dapat diikuti setelah menyelesaikan C3 => C6, C7, C9, C10
Buang C3 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C4 => C14
Karena C14 sudah dipelajari, maka tidak usah dimasukkan
Buang C4 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C14 => C5
Buang C14 dalam antrian
Antrian : [ ]
Masukkan C5, C6, C7, C9, C10 ke dalam antrian
Antrian : [C5, C6, C7, C9, C10], waktu = 9 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C5 => C8
Buang C5 dari antrian
- Kursus yang dapat diikuti setelah menyelesaikan C6 => tidak ada
Buang C6 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C7 => tidak ada
Buang C7 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C9 => tidak ada
Buang C9 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C10 => C11
Buang C10 dalam antrian
Antrian : [ ]
Masukkan C8, C11 ke dalam antrian
Antrian : [C8, C11], waktu = 12 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C8 => tidak ada
Buang C8 dalam antrian
- Kursus yang dapat diikuti setelah menyelesaikan C11 => C12
Buang C11 dalam antrian
Antrian : [ ]
Masukkan C12 dalam antrian
Antrian : [C12], waktu = 15 bulan
- Kursus yang dapat diikuti setelah menyelesaikan C12 => tidak ada
Buang C12 dalam antrian
Antrian : [ ]
Semua kursus sudah diikuti dan algoritma berhenti
Jawab : 15 bulan
SUMBER COPY PASTE = Bhttp: //sma-olimpiade.blogspot.co.id/2014/06/kumpulan-soal-olimpiade-komputer-sma.html
