[Leetcode] Keys and Rooms (BFS/DFS) - java

Keys and Rooms - LeetCode

문제 파악

각 방에는 다음 방으로 갈 수 있는 열쇠가 있음.

모든 방을 탐색하면 true, 그렇지 않으면 false를 반환하는 문제

 

입출력 예시

Input: rooms = [[1],[2],[3],[]]
Output: true

 

설명:

• 0번 방을 방문해서 1번 열쇠를 획득
• 1번 방 방문후 2번 열쇠 획득
• 2번 방 방문 후 3번 열쇠를 획득
• 3번 방 방문을 마지막으로 방 탐색 종료, 모든 방 탐색을 마쳤으므로 true 반환

 

---

접근 방법

다음 방으로 넘어가고 탐색하는 것은 BFS/DFS로 쉽게 구현할 수 있지만 모든 방을 탐색했을 때 확인하는 것이 까다로운 문제이다.

그래서 기존 방식처럼 배열 형태가 아닌 HashSet을 이용해서 방문처리를 하여 모든 방을 방문했을 경우 HashSet의 크기가 모든 방의 개수와 동일할 경우 모든 방을 탐색했다는 것으로 true를 반환하면 된다.

1. 방 탐색은 BFS나 DFS로 진행
2. 방문처리를 HashSet으로 구현
3. 모든 방을 방문했을 때 (방문셋과 방의 크기가 동일) 종료

---

코드 구현

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> visited = new HashSet<>();

        dfs(rooms, 0, visited);

        // 모든 방을 방문했을 때 true 반환
        if(visited.size() == rooms.size()){
            return true;
        }
        else return false;
    }
    public void dfs(List<List<Integer>> rooms, int cur, Set<Integer> visited){
        // 1. 현재 노드 방문 처리
        visited.add(cur);

        // 2. 다음 노드 예약
        for(int i : rooms.get(cur)){
            if(!visited.contains(i)){
                dfs(rooms, i, visited);
            }
        }
    }
}

---

배우게 된 점

HashSet을 이용해서 방문처리를 했을 때의 장점을 느낄 수 있던 문제였던 것 같다.

그리고 풀면서 실수했던 부분이 다음 노드 예약 과정에서 현재 노드 기준으로 다음 탐색할 인덱스를 불러와야 하는데
반복문을 i = 0; i < rooms.size(); 를 한다던지, rooms.get(i)를 한다는 등의 실수를 했다.

 

실수하지 않고 잘 작성하는 연습을 해야겠다.