Ada sayısı

Problem

'1' (kara) ve '0' (su) karakterlerinden oluşan bir harita ızgarası veriliyor. Yatay ya da dikey olarak birbirine değen kara hücreleri aynı adaya aittir; çapraz komşuluk sayılmaz. Izgaranın dışı su kabul edilir. Haritadaki ada sayısını döndür.

1 1 0 0 0
1 1 0 1 0
0 0 0 1 0
1 0 0 0 0

Çıktı: 3   (sol üstteki 2x2 blok, sağdaki dikey ikili, sol alttaki tek hücre)

1 0 1
0 1 0
1 0 1

Çıktı: 5   (çapraz değmeler ada birleştirmez)

Netleştirme soruları

• Komşuluk 4 yönlü mü, 8 yönlü mü? (4 yönlü.)
• Girdi ızgarasını değiştirebilir miyim? (Ziyaret işareti için hücreleri '0' yapmak yaygın ama çağıranın verisini bozar; sormak gerekir.)
• Izgara boyutu ne? (LeetCode'da 300x300'e kadar; bu, özyinelemeli DFS'in stack'i taşırıp taşırmayacağını belirler.)
• Izgara boş (0 satır) olabilir mi?
• Harita sonradan güncellenecek mi (kara eklenecek mi)? (Öyleyse Union-Find daha uygun; takip sorusu.)

İpuçları

Yaklaşım

Bu, "bağlı bileşen sayısı" probleminin ızgara halidir.

Dolaşım (flood fill): Tüm hücreleri sırayla gez; ziyaret edilmemiş bir kara hücre bulunca sayacı artır ve oradan BFS/DFS ile ulaşılabilen tüm kara hücreleri işaretle. Her hücre en fazla bir kez işaretlendiği için toplam iş hücre sayısıyla orantılıdır.

Özyinelemeli DFS mi, iteratif BFS mi? Özyinelemeli DFS en kısa koddur ve mülakatların çoğunda kabul görür. Ancak tamamen karadan oluşan 300x300 bir ızgarada özyineleme derinliği 90.000'e kadar çıkabilir. Bu çözümün testinde, varsayılan 1 MB stack'le özyinelemeli DFS bu ızgarada StackOverflowError verdi. İteratif BFS (ya da açık stack'li DFS) bu riski taşımaz. Mülakatta özyinelemeli yazsan bile bu riski söylemek iyi bir sinyaldir.

Union-Find alternatifi: Her kara hücreyi bir küme yap, sağ ve alt komşusu karaysa birleştir; sonunda kök sayısı ada sayısıdır. Statik ızgara için dolaşımdan daha karmaşıktır, ama harita dinamik olarak değişiyorsa (kara ekleniyorsa) doğru araçtır.

Girdiyi değiştirmek: Hücreyi '0' yaparak "batırmak" ek O(mn) bellekten tasarruf eder ama yan etkidir. Aşağıdaki çözüm ayrı bir visited dizisi kullanır; bellek kısıtı sıkıysa batırma tercih edilebilir, yeter ki çağıranla netleştirilmiş olsun.

Java çözümü

import java.util.ArrayDeque;

public final class NumberOfIslands {

    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int numIslands(char[][] grid) {
        if (grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];   // girdiyi değiştirmemek için ayrı işaret
        int islands = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    islands++;                            // yeni bir adanın ilk hücresi
                    markIsland(grid, visited, r, c);
                }
            }
        }
        return islands;
    }

    /** İteratif BFS: özyinelemeli DFS büyük ızgarada StackOverflowError verebilir. */
    private void markIsland(char[][] grid, boolean[][] visited, int startRow, int startCol) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        visited[startRow][startCol] = true;
        queue.offer(new int[]{startRow, startCol});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : DIRECTIONS) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length
                        && grid[r][c] == '1' && !visited[r][c]) {
                    visited[r][c] = true;                 // kuyruğa EKLERKEN işaretle
                    queue.offer(new int[]{r, c});
                }
            }
        }
    }
}

Hücreyi kuyruktan çıkarırken değil eklerken işaretlemek önemlidir. Aksi halde aynı hücre birden fazla komşusu tarafından kuyruğa eklenir; sonuç yine doğru çıkar ama kuyruk ve süre gereksiz büyür.

Karmaşıklık

• Zaman: O(m·n). Her hücre dış döngüde bir kez okunur, BFS'te en fazla bir kez kuyruğa girer ve 4 komşusu kontrol edilir.
• Bellek: O(m·n) visited dizisi; girdiyi batırma yöntemiyle kaldırılabilir. BFS kuyruğu tamamen kara bir dikdörtgende O(min(m, n)) mertebesinde kalır (dalga cephesi bir köşegen), ama çok dallanan bir ada şeklinde aynı mesafedeki hücre sayısı alanla orantılı olabilir; en kötü durum O(m·n). Özyinelemeli DFS'te en kötü O(m·n) stack.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Örnek harita: 3.
• Ortası su olan halka (111 / 101 / 111): 1 ada.
• Çapraz desen: 5 (çapraz komşuluk sayılmıyor).
• Tamamı su: 0; tek kara hücre: 1; 0 satırlı ızgara: 0.
• Girdi ızgarası çağrıdan sonra değişmemiş.
• 500 rastgele ızgara (1-12 boyut), özyinelemeli DFS referansıyla karşılaştırıldı.
• 300x300 tamamı kara: 1 ada; aynı ızgarada özyinelemeli referans StackOverflowError verdi, iteratif çözüm sorunsuz.

Mülakatçı için

Bu soru çoğu şirkette ilk graf sorusudur ve 20 dakikada bitmesi beklenir. Asıl ayırt edici noktalar: adayın problemi "bağlı bileşen" olarak adlandırması, sınır kontrollerini temiz yazması (yön dizisi kullanmak, dört ayrı if yerine), ziyaret işaretinin zamanlaması ve girdi değişikliğini sorması.

İpucu zamanlaması: Aday 3-4 dakikada graf benzetmesini kuramazsa ilk ipucunu ver. İkinci ve üçüncü ipucu genelde gerekmez; gerekiyorsa adayın graf dolaşımı temeli zayıftır, bunu not et. Aday özyinelemeli DFS yazarsa çözüm bittikten sonra "300x300 tamamı kara olursa ne olur?" diye sor.

Takip sorusu 1: Kara hücreler tek tek ekleniyor; her eklemeden sonra ada sayısını döndür. Beklenen: Union-Find; yeni hücre için sayaç +1, karaya değen her komşuyla başarılı birleştirmede -1. Her ekleme neredeyse O(1) (amortize α(n)); her seferinde yeniden dolaşmak O(k·m·n) olurdu (LeetCode 305).

Takip sorusu 2: En büyük adanın alanını döndür. Beklenen: dolaşım sırasında hücre sayısını tutmak, maksimumu güncellemek (LeetCode 695).

Takip sorusu 3: Izgara bellek dışı, satır satır stream ediliyor. Beklenen: sadece önceki ve şu anki satırı tutup Union-Find ile satırlar arası birleştirme; tamamlanan (bir sonraki satıra değmeyen) bileşenleri sayıp bırakmak.

Benzer problemler

• Max Area of Island (LeetCode 695)
• Number of Islands II (LeetCode 305)
• Surrounded Regions (LeetCode 130)
• Rotting Oranges (LeetCode 994)
• Number of Provinces (LeetCode 547)