BFS | LeetCode - 841. Keys and Rooms java

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

 

 

0부터 n-1까지의 번호가 붙은 방들이 있고, 잠겨있는 방 문을 열기 위해서는 각 방에 놓여있는 방 번호와 일치하는 열쇠로 문을 열 수 있다.

모든 방은 잠겨있으므로 열쇠가 필요하다.

 

2차원 배열이 주어지고, 배열의 1차원 인덱스는 각 방의 번호를, 2차원 인덱스의 요소들은 열쇠를 뜻한다.

예를 들어 다음과 같은 배열이 주어진다면,

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

 

rooms[0] = {1,2} 이므로, 0번째 방에서는 1번 방과 2번 방을 갈 수 있는 열쇠를 얻을 수 있음을 뜻한다.

 

이러한 상황에서 가장 많은 방을 탐색할 수 있는 경우의 방 개수를 구하는 문제이다.

 

이 문제는 인접 리스트로 구현된 그래프 탐색 문제를 푸는 방식으로 문제를 해결할 수 있으므로 bfs로 해결할 수 있었다.

 

class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //bfs
        Map<Integer, Boolean> chk = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < rooms.get(0).size(); i++) {
            q.offer(rooms.get(0).get(i));
            chk.put(0, true);
        }

        while (!q.isEmpty()) {
            int curr = q.poll();
            chk.put(curr, true);
            for (int next : rooms.get(curr)) {
                if (!chk.containsKey(next)) {
                    q.offer(next);

                }
            }
        }

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

 

 

동일한 방을 중복 탐색할 필요가 없으므로 무한 루프를 방지하기 위해 방문을 체크하는 map을 선언하고, 열쇠를 받아 탐색할 수 있도록 queue를 선언하였다.

Map<Integer, Boolean> chk = new HashMap<>();
Queue<Integer> q = new LinkedList<>();

 

방 탐색은 0번 방부터 시작하므로 0번 방에서 얻을 수 있는 열쇠를 queue에 담고 탐색을 시작하였다.

for (int i = 0; i < rooms.get(0).size(); i++) {
    q.offer(rooms.get(0).get(i));
    chk.put(0, true);
}

 

다음 방으로 갈 수 있는 여부는 다음과 같은 요소에 의해 결정된다.

1. 열쇠가 있는지

2. 모든 방을 탐색하진 않았는지

 

1번의 경우는 얻은 열쇠를 모두 queue에 넣어(인벤토리라고 생각해도 될 것 같다.) 다음으로 갈 수 있는 방을 체크하면 되고, 2번의 경우에는 방문한 방을 기록하여 이전에 방문한 방이 주어진 방 개수(rooms.size()) 와 같아지는지 체크하면 된다.

 

 while (!q.isEmpty()) {
    int curr = q.poll();
    chk.put(curr, true);
    for (int next : rooms.get(curr)) {
        if (!chk.containsKey(next)) {
            q.offer(next);

        }
    }
}

if (chk.size() != rooms.size()) {
    for(int i = 0; i<rooms.size(); i++) {
        if(!chk.containsKey(i)) {
            return false;
        }
    }
}