題目描述:有 n 間房間,編號為 0 到 n-1。初始時只有房間 0 是解鎖的,其餘房間都是上鎖的。每間房間裡面有一組鑰匙,每把鑰匙對應另一間房間的編號,持有該鑰匙就可以解鎖並進入對應的房間。給定一個 rooms 陣列,其中 rooms[i] 是在第 i 間房間找到的鑰匙列表,請判斷能否訪問所有的房間。
解題思路:這道題本質上是一個圖的可達性問題。將每間房間視為圖中的節點,鑰匙代表有向邊(房間 i 有鑰匙 j,表示存在 i → j 的邊)。問題轉化為:從節點 0 出發,能否到達圖中所有節點?
使用 DFS(深度優先搜尋) 從房間 0 開始遍歷:
visited 集合記錄已訪問的房間。visited 的大小等於 n,代表所有房間都能到達,回傳 true;否則回傳 false。關鍵觀察:進入一間房間才能拿到裡面的鑰匙,因此必須從已能訪問的房間出發,逐步擴展可達範圍,這正是 DFS/BFS 的典型應用場景。
時間複雜度:O(N + K) — 其中 N 為房間數量,K 為所有房間中鑰匙的總數量。每間房間最多被訪問一次,且每把鑰匙最多被檢查一次,相當於遍歷整張圖的所有節點與邊。
空間複雜度:O(N) — visited 集合最多儲存 N 個房間編號,遞迴呼叫堆疊最深也不超過 N 層(在最壞情況下,房間形成一條鏈時),因此空間複雜度為 O(N)。
1. Initialize an empty set `visited`.
2. Call dfs(rooms, room=0, visited).
a. Add `room` to `visited`.
b. For each `key` in rooms[room]:
- If `key` is not in `visited`, call dfs(rooms, key, visited).
3. After dfs returns, check if size of `visited` equals total number of rooms.
a. If yes, return true (all rooms reachable).
b. If no, return false (some rooms are unreachable).BFS(廣度優先搜尋)O(N + K):使用佇列(queue)取代遞迴堆疊。從房間 0 開始,將其加入佇列並標記為已訪問。每次從佇列取出一間房間,遍歷其所有鑰匙,若對應的房間尚未訪問,則加入佇列並標記。重複此過程直到佇列為空。最終判斷已訪問房間數是否等於 n。BFS 和 DFS 的時間與空間複雜度相同,但 BFS 使用迭代方式,避免在房間數量極大時可能發生的遞迴堆疊溢出問題。
Iterative DFS O(N + K):使用顯式的 stack 模擬 DFS,邏輯與 BFS 相似,差別在於使用後進先出(LIFO)的 stack 而非先進先出(FIFO)的 queue,走訪順序與遞迴 DFS 一致,同樣可避免遞迴深度限制的問題。
0 出發訪問所有可達房間的最小總花費,應使用哪種演算法?(提示:Dijkstra 或 0-1 BFS。)