###### tags: `Leetcode` `medium` `graph` `bfs` `dfs` `python` `c++`

# 841. Keys and Rooms

## [題目連結:] https://leetcode.com/problems/keys-and-rooms/description/

## 題目:
There are n rooms labeled from ```0``` to ```n - 1``` and all the rooms are locked except for room ```0```. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of **distinct keys** in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array ```rooms``` where ```rooms[i]``` is the set of keys that you can obtain if you visited room ```i```, return ```true``` if you can visit **all** the rooms, or ```false``` otherwise.

**Example 1:**

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

**Example 2:**

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

## 解題想法:
* 此題為給定房間，房間內有鑰匙，可以打開對應的位置
* 從起始0號位置開始，求是否能遍歷所有房間
* 以ex2而言:
* 可以自己連自己

* 原本搞錯以為與 [207. Course Schedule](/txZn8rNCReWvEPygWnh-Zg) 概念一樣
* 結果自作多想根本不需要判斷indegrees><
* 解法:
* **BFS有向圖遍歷即可**
* Step1:
* 建立邊
* visited=set() 紀錄已拜訪過的點
* Step2:
* que=[0] 從0開始拜訪
* num=0 紀錄目前已拜訪數量
* while進行判斷
* 每次拜訪到新的點時，num+=1
* Step3:
* 最終判斷 num==len(graph)即可
* 也可以用DFS遞迴判斷~~

## Python_Sol1: BFS

from collections import defaultdict
class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        #遍歷是否能通過所有點
        #BFS: 每次找鄰居的點
        graph=defaultdict(list)
        visited=set() #紀錄已拜訪過的
        visited.add(0)
        #connect the graph
        for u,item in enumerate(rooms):
            for v in item:
                graph[u].append(v) # u->v
        que=[0] #因為0本身可以進去，從0開始
        num=0 #紀錄已拜訪數量
        #BFS
        while que:
            curNode=que.pop(0)
            num+=1
            for neighber in graph[curNode]:
                if neighber not in visited:
                    visited.add(neighber)
                    que.append(neighber)
        return num==len(graph)

## Python_Sol2: DFS

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        #遍歷是否能通過所有點
        self.visited=set()
        self.num=0
        self.dfs(rooms,0)
        return self.num==len(rooms)
        
    def dfs(self,rooms,curPos):
        self.num+=1
        self.visited.add(curPos)
        for neighber in rooms[curPos]:
            if neighber not in self.visited:
                self.dfs(rooms,neighber)

## C++_Sol1: BFS

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        unordered_map<int, vector<int>> graph;
        unordered_set<int> visited;
        visited.insert(0);
        //connect the graph
        for (int u=0; u<rooms.size(); u++){
            for (auto v: rooms[u]) graph[u].push_back(v);
        }
        queue<int> que;
        que.push(0);
        int num=0,curNode;
        //BFS
        while (!que.empty()){
            curNode=que.front(); que.pop();
            num+=1;
            for (auto neighber: graph[curNode]){
                //cant find in set
                if (visited.find(neighber)==visited.end()){
                    visited.insert(neighber);
                    que.push(neighber);
                }
            }
        }
        return num==rooms.size();
    }
};

## C++_Sol2: DFS

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        dfs(rooms,0);
        return num==rooms.size();
    }

    void dfs(vector<vector<int>>& rooms, int curPos){
        visited.insert(curPos);
        num+=1;
        for (auto neighber: rooms[curPos]){
            if (visited.find(neighber)==visited.end())
                dfs(rooms,neighber);
        }
    }

private:
    unordered_set<int> visited;
    int num=0; //num of already visited rooms
};