從LeetCode學演算法 - 45 DFS (1)

0200 Number of Islands (Medium)

寫在前面： 如果覺得這篇有幫助到您的話， 請幫我隨手點開最下面的SHOW EMBED並拍5下手~ (當然，Medium的拍手也可以多拍幾下啦XD) 這樣我再寫個十多篇以後應該就有買一杯咖啡的$$了XDDDDD (聽起來超少哈哈)

Question: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

分析/解題： 給定一個二維的地圖當中陸地用'1'表示，水則用'0'表示， 試計數這整張圖有多少島嶼(island)。可假定地圖的外圍均為水域。 (島嶼的定義就是其周圍都圍繞著水， 且可以通過連接相鄰的垂直/水平陸地所構成。)

如對於題目描述依舊沒搞懂的話，就把它當成小畫家填色的色塊吧！ 視為相同區域的用油漆桶可以全部填滿XD 而題目所問的，就相當於要填幾次才能將所有陸地區域填滿。

對於要確認島嶼這點，只有一種方法： 每次從一個點開始向外延伸相鄰的格子， 直到周圍沒有可以延伸的區域為止。 這時候這整塊區域就是我們所謂的島嶼，於是計數可以加1。 那麼問題來了，在延伸的過程中一共有四個方向可以選擇， 如果不加限制的話，無疑會有重複的部分； 所以除了檢查是否遇到水(‘0’，也就是可以不用繼續往下搜尋)外， 我們還需要知道這個格子是否已經走過了。 所以我們會再新增一個visited陣列用來標明已經走過的區域。 (這樣子只要已經走過的就直接跳過即可。)

由於每次會需要走到底才會回頭， 所以這種方式是很典型的DFS(Depth-First Search，深度優先搜尋)方法。

所以流程會變成： 1. 初始化一個visited二維陣列，預設當中每個值均為false 2. 對grid中的每個點(i, j)檢查其是否為陸地(‘1’)，且未曾走訪過的話: 2-a. 遞增島嶼計數值，並從每個點(i, j)呼叫函式dfs來開始走訪 3. 在dfs中，先檢查(i, j)點是否符合規範(因會+1或-1，須不超出範圍)， 且尚未走訪過(visited[i][j] == false)的狀況，進行3-a的流程 3-a. 將visited[i][j]設定為true 3-b. 往(i, j)的上下左右走，並傳入下一階段的dfs。

這麼一來，當整張圖掃過去以後， 我們就能知道到底有幾個島嶼了！

Java和Python的寫法基本一致，這邊不再贅述， 讀者只要注意到應該被檢查的邊界條件即可。

Java:

Python:

在這個範例中我們使用了一個額外的陣列來儲存， 有沒有辦法能夠不用額外的陣列呢？ 其實是有的，辦法就是將每次走過的陸地(‘1’)， 都直接設定成水(‘0’)，自然就相當於都走過了， 從而可以替代掉用visited來處理。 優點是速度會較為快速， 但很嚴重的缺點是這麼做完以後， grid本身就會變成全部都是’0'的陣列了。 除非已經確定這個grid可以被任意操作， 否則筆者認為要這麼做的話記得要先問清楚要求才下手才行XD~

此外，這題在返回時仍舊要保留走過哪些格子的資訊， 所以和之前的Backtracking的題目作法是不一樣的。

面試實際可能會遇到的問題： 「時間/空間複雜度？」 (若m, n為長寬，O(m*n) for best case，理論上全部走訪一遍即可, O(m*n)) (如果可以清空grid則記錄用的空間複雜度是O(1)) (若考慮call stack的部份的話，總空間複雜度worst case是O(N))

相似及延伸： 1. 0130. Surrounded Regions 2. 0695. Max Area of Island

Special Thanks suggestions/corrections from viewers: Raiy Kuo: DFS時recusive占用的stack應一併考慮進去。

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

如果你／妳覺得這篇文章不錯，請給我5個拍手，並且給我5個Like。(點開SHOW EMBED!)
如果你／妳非常喜歡這篇文章，可以按著拍手直到50下。
也請記得「Follow」我，隨時收看最新的文章。