[알고리즘] 11, 12번째 문제

[SongGwanSeok]

📝 Description

무엇을? 11번째

• https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 12번째
• https://leetcode.com/problems/keys-and-rooms/description/
• https://leetcode.com/problems/bus-routes/description/

왜?

• (ex 사용자를 인증하기 위해)

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[SongGwanSeok]

https://leetcode.com/problems/keys-and-rooms/description/

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        deque<int> q;
        q.push_back(0);

        while(!q.empty()){
            int now = q.front();
            q.pop_front();
            visited[now] = true;
            vector<int> keys = rooms[now];

            for(int key: keys){
                if(!visited[key]){
                    q.push_back(key);
                }
            }
        }

        for(bool v: visited){
            if(!v){
                return false;
            }
        }
        return true;
    }
};

---

class Solution {
public:
    void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int now){
        visited[now] = true;
        vector<int> keys = rooms[now];

        for(int key: keys){
            if(!visited[key]){
                dfs(rooms, visited, key);
            }
        }
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {

        vector<bool> visited(rooms.size(), false);

        dfs(rooms, visited, 0);

        for(bool v: visited){
            if(!v){
                return false;
            }
        }
        return true;
    }
};