CP #4 : Number of Islands Problemi
Problem surada.
Cozum
Verilen grid'i bir graph olarak dusunebiliriz. Bir adayi tespit etmek icin, bir degeri 1 olan hucreden yola cikarak yavas yavas komsularini kontrol ederek disari dogru genisletebiliriz. Bu da aslinda breadth first search anlamina geliyor.
Cozum adimlari soyle olacak:
1. Gridinin 0,0 noktasindan baslayarak 2 for loop icerisinde tum node'larini itere edecegiz.
2. Ayni node'u 2 veya daha fazla kere ziyaret etmememiz gerekiyor, bunun icin ziyaret edilen node'lari tutacagimiz bir set olusturacagiz
3. Eger hucre degeri 1 ise, ada sayisini 1 artirip, buradan disari dogru genisletme islemi baslayacak (tabi ziyaret edilmemis node'lar uzerinden)
4. bir arama basladiktan sonra, bir noktada eklnen tum komsular 0 olunca (ada bitti), arama sonlanacak
Implementasyon
Bir node'u ziyaret ederken komsularini bulmamiz gerekiyor. Bu noktada bazi edge case'ler var. Iste node en solda ise, onun solunda bir hucre yoktur meselea. Ya da node en sagda ise onun saginda node olmamasi gibi. Bunlari handle edecek bir helper fonk yaziyorum:
Bu arada tum kod boyunca x stun, y ise satir indexi olacak.
visited = set() # ziyaret edilen node'larin (x,y) indexlerini tututlan set
def get_node(x, y):
if x < 0 or x >= len(grid[0]) or y < 0 or y >= len(grid) or (x,y) in visited:
return None
else:
visited.add((x,y))
return (x, y)
Daha sonra bir node icin potansiyel 4 komsunu getiriyorum:
def get_neighbors(x, y):
nodes = [ get_node(x, y-1),
get_node(x-1, y), get_node(x+1, y),
get_node(x, y+1)
]
return [n for n in nodes if n is not None]
seklinde bir node'un 4 tarafina bakiyorum. Egere node var ise donecek, yok ise None donecek. None olanlari da ikinci adimda filtreliyorum. Ve geriye valid komsular kaliyor. Bu sayede mesela en sol ust kose icin sadece 2 komsu dondurebiliyoruz.
Simdi grid'i taramaya gecebiliriz.
island_count = 0
for i in range(len(grid[0])):
for j in range(len(grid)):
if grid[j][i] == "1" and (i, j) not in visited:
# hemen ada sayisini artirabilirim
# cunku arama basladiktan sonra zaten komsulari visited'e ekledigim icin
# arama bitmeden (bir ada bitmeden) digerine gecmeyecegiz
island_count += 1
# bfs yapmak icin bir que baslatiyorum
q = degue([(i, j)])
while q:
# que'nun en basindaki elemani kopariyorum ve komsularini kontrl edip
# 1 olan komsularini tekrar queue'ya ekliyorum
(x, y) = q.popleft()
neighbors = get_neighbors(x, y)
for (nx, ny) in neighbors:
if q[nx][ny] == "1":
q.append((nx, ny))
# buraya geldigimizde demek ki que'da hic 1 kalmamis ve adanin sinirlarina gelinmis,
# yani ada bitmis
return island_count
Breadth first search
Bu ornekte oldugu gibi eger amacimiz bir graph node'undan yola cikarak yavas yavas her yone dogru ilerlemek ise breadth first search kullaniriz. Adi uzerinde, once genislik. Ama amacimiz ilk once sadece tek bir yonde yol bitinceye kadar ilerlemek ise bu durumda depth first search kullaniriz. (Adi uzerinde, derinlik once, onun meshur robotun yol bulma problmei vardir ki ileride cozecegiz).
Breadth first search yapmak icin ornekte de gorduk ki bir que yapisina ihtiyacimiz var. Neden?
1. En basta sadece bir node'dan basliyoruz.
2. Ikinci adimda tek node'un komsularini aldigimizda elimizde 4 veya daha fazla (capraz komsuluk iliskisi de olabilir ya da graph topolojisi cok farkli olabilir) node oluyor
3. sonra bunlarin da komsularina bakmamiz gerekiyor. Ve bazilari valid komsuya sahip olmuyor. Bu ornekteki 0 degerine sahip olan node'lar gibi.
4. Tum bu komsulari que'ya atip, diger adimda que'nun en basindaki elemani kopartarak islem yapiyoruz. Bir noktada que'daki elemanlar bitiyor ve biz istedigimiz kritere gore bir node'dan baslayarak disariya dogru, her yone, arama yapmis oluyoruz.
Analiz
Catara cutara bu problemi cozdukten sonra time compl. degerine bir bakalim:
- Her node'u bir kere ziyaret ettigimiz icin O(M x N) seklinde (m satir, n stun sayisi)
- Ziyaret edilenleri tutacak bir set icin yine lineer bir hafiza geereksinimi O(M x N)
Yani tamamen lineer bir cozum elde etmisiz. Diger soruda gorusmek uzere.
Yorumlar
Yorum Gönder