LeetCode (C/C++, Java) 841. Keys and Rooms

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

---

풀이

0번 방부터 dfs로 탐색하며 방문 가능한 방을 모두 탐색한다. 이 때 방문 여부를 저장해, 미리 방문한 방은 다시 탐색하지 않는다.

모든 방을 탐색한 후 탐색하지 않은 방이 있다면 false, 모든 방을 탐색했다면 true를 반환한다.

---

C/C++ 코드

class Solution {
public:
    bool visited[1001] = {false, };
    void dfs(vector<vector<int>>& rooms, int now) {
        if (visited[now]) return;

        visited[now] = true;
        for (int next : rooms[now]) 
            dfs(rooms, next);
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        dfs(rooms, 0);

        for (int i = 0; i < rooms.size(); i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
};

 

Java 코드

class Solution {
    private boolean[] visited;

    private void dfs(List<List<Integer>> rooms, int now) {
        if (visited[now]) return;

        visited[now] = true;
        for (int next : rooms.get(now))
            dfs(rooms, next);
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int size = rooms.size();
        visited = new boolean[size];

        dfs(rooms, 0);
        for (int i = 0; i < size; i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
}