Number of Islands
Kamu mendapatkan peta berupa list string yang panjangnya sama, dengan '1' sebagai kotak daratan dan '0' sebagai kotak air. Dua kotak daratan termasuk pulau yang sama jika berbagi sisi: atas, bawah, kiri, atau kanan. Kotak yang hanya bertemu di sudut tidak terhubung. Kembalikan jumlah pulau.
Fungsi
- gridstring-array
- peta, satu string per baris
- Mengembalikaninteger
- jumlah pulau
Batasan
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- Setiap baris memiliki panjang yang sama.
- Setiap karakter adalah
'0'atau'1'.
Contoh
- Input
- grid = ["11000", "11000", "00100", "00011"]
- Output
- 3
- Penjelasan
- Empat kotak di kiri atas membentuk satu pulau. Kotak tengah pada baris ketiga hanya bersentuhan dengan kotak-kotak itu di sudut, jadi itu adalah pulau kedua. Sepasang kotak di kanan bawah adalah pulau ketiga.
- Input
- grid = ["01110", "01000", "00011", "11001"]
- Output
- 3
- Penjelasan
- Tiga kotak di baris teratas dan satu kotak di bawah ujung kirinya membentuk satu pulau. Sepasang kotak di sisi kanan baris ketiga terhubung ke bawah hingga kotak di kanan bawah, membentuk pulau kedua. Sepasang kotak di kiri bawah adalah pulau ketiga.
Pertanyaan lanjutan
Tanah kini muncul satu petak setiap kali di peta perairan. Bisakah kamu melaporkan jumlah pulau setelah setiap petak baru muncul tanpa memindai seluruh peta lagi?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Pindai peta petak demi petak. Saat kamu mencapai petak daratan yang belum diklaim oleh pulau mana pun sebelumnya, berapa banyak pulau baru yang kamu temukan?
Setelah menemukan pulau baru, kunjungi setiap petak daratan yang terhubung dengannya dan tandai setiap petak sebagai sudah dilihat, agar pemindaian tidak menghitung pulau yang sama lagi.
Jelajahi dengan queue (breadth first) atau stack eksplisit (depth first) yang berisi kotak-kotak yang belum dikunjungi. Pencarian rekursif bisa kehabisan call stack pada peta yang terdiri dari satu pulau besar, sedangkan perulangan dengan queue atau stack buatanmu sendiri tidak akan kehabisan call stack.
Solusi
Anggap setiap kotak daratan sebagai simpul yang terhubung dengan kotak daratan di sebelahnya: sebuah pulau adalah satu bagian yang saling terhubung. Telusuri peta, dan setiap kali kamu menemukan daratan yang belum pernah kamu lihat, hitung satu pulau baru lalu lakukan flood fill pada pulau itu, tandai setiap kotaknya agar penelusuran tidak menghitungnya lagi.
Flood fill dengan stack eksplisit (DFS)
Intuisi
Kotak daratan yang belum ditandai tidak mungkin termasuk pulau yang sudah kamu hitung, karena penghitungan pulau akan menandai seluruh bagiannya. Jadi, kotak itu memulai pulau baru. Tumpukan yang kamu kelola sendiri akan menandai sisanya: setiap kotak yang kamu keluarkan dari tumpukan akan memasukkan tetangga daratannya yang belum ditandai ke dalam tumpukan, dan saat tumpukan kosong, seluruh pulau sudah ditandai.
Tumpukan buatanmu sendiri penting karena pengisian rekursif dapat mencapai kedalaman 22,500 pemanggilan pada peta daratan penuh berukuran 150 × 150. Setiap kotak dimasukkan ke tumpukan paling banyak satu kali dan memeriksa empat tetangga, sehingga waktunya O(rows × cols). Penanda dan tumpukan membutuhkan ruang O(rows × cols) saat seluruh peta berupa daratan.
Algoritma
- Buat penanda sudah dikunjungi untuk setiap kotak dan atur hitungannya ke 0.
- Pindai setiap kotak, lewati air dan kotak yang sudah dikunjungi.
- Di tanah yang belum dikunjungi, tambahkan 1 ke hitungan, tandai kotaknya, lalu masukkan ke tumpukan.
- Selama tumpukan tidak kosong, keluarkan satu kotak lalu masukkan setiap tetangganya yang berada di dalam peta dan merupakan tanah yang belum dikunjungi, tandai sebelum memasukkannya.
- Kembalikan hitungannya saat pemindaian selesai.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countFlood fill dengan queue (BFS)
Intuisi
Penghitungannya tetap sama, hanya urutan kunjungannya yang berubah. Queue mengambil kotak dari depan dan menambahkan tetangga daratan yang belum ditandai ke bagian belakang, sehingga mengunjungi pulau dalam beberapa lapisan: kotak pertama, lalu setiap kotak yang berjarak satu langkah, kemudian yang berjarak dua langkah. Setiap kotak tetap dikunjungi satu kali, dengan waktu dan ruang O(rows × cols).
Urutan lapisan menunjukkan jarak setiap kotak dari titik awal, sehingga perulangan yang sama dapat menjawab pertanyaan tentang jalur terpendek pada grid dengan satu angka tambahan untuk setiap kotak.
Algoritma
- Buat penanda kunjungan untuk setiap kotak dan tetapkan hitungan ke 0.
- Pindai setiap kotak, lewati air dan kotak yang sudah ditandai.
- Di daratan yang belum ditandai, tambahkan 1 ke hitungan, tandai kotak tersebut, lalu masukkan ke antrean kosong.
- Selama antrean berisi kotak, ambil satu dari bagian depan dan tambahkan setiap tetangganya yang berada di dalam peta dan merupakan daratan yang belum ditandai ke bagian belakang antrean, lalu tandai saat menambahkannya.
- Kembalikan hitungan saat pemindaian selesai.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
Jebakan dan kasus tepi
- Menandai kotak saat mengeluarkannya dari stack atau queue, bukan saat memasukkannya. Kotak yang sama kemudian masuk beberapa kali.
- Membandingkan kotak dengan angka 1, bukan karakter
'1'. Setiap baris adalah string, jadi setiap kotak adalah karakter. - Membaca tetangga sebelum memeriksa
0 ≤ row < rowsdan0 ≤ col < cols. Kotak daratan di tepi kemudian membaca di luar peta. - Menulis pengisian secara rekursif. Secara default, Python berhenti setelah 1.000 pemanggilan, dan bahasa lain bisa mengalami stack overflow pada satu pulau besar.
- Mengambil bagian depan list Python dengan
pop(0), yang membutuhkan waktu sebanding dengan panjang list. Gunakancollections.dequedanpopleft().
Pertanyaan yang sering diajukan4
Apa kompleksitas waktu dari Number of Islands?
O(rows × cols). Pemindaian memeriksa setiap petak satu kali, dan setiap petak daratan masuk ke stack atau queue satu kali serta memeriksa empat tetangga. Penanda seen dan stack atau queue menggunakan ruang O(rows × cols) pada peta yang seluruhnya berupa daratan.
Haruskah kamu menggunakan BFS atau DFS untuk Number of Islands?
Keduanya benar dengan waktu dan ruang yang sama, karena penghitungannya hanya perlu menandai setiap kotak di sebuah pulau. BFS dengan queue tidak pernah menggunakan rekursi. DFS sama amannya jika menggunakan stack eksplisit.
Bisakah kamu menyelesaikan Number of Islands dengan union-find?
Ya. Masukkan setiap kotak daratan ke dalam set tersendiri dan mulai hitungan dari jumlah kotak daratan. Gabungkan setiap pasangan kotak daratan yang bertetangga, lalu kurangi hitungan satu setiap kali penggabungan menghubungkan dua set yang berbeda. Dengan kompresi jalur, waktunya mendekati O(rows × cols).
Bisakah kamu menghitung pulau tanpa array seen yang terpisah?
Ya, jika kamu boleh mengubah peta: ubah setiap petak daratan menjadi air begitu kamu mencapainya. Banyak bahasa tidak bisa mengubah string secara langsung, jadi kamu menyalin baris-barisnya ke dalam kisi karakter terlebih dahulu, yang membutuhkan ruang sebanyak tanda yang sudah dilihat.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def numIslands(grid):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
grid = ["11000", "11000", "00100", "00011"]
Output yang diharapkan
3