Keys and Rooms (BFS)

이번 문제는 LeetCode의 Queue, Stack 튜토리얼의 마지막 문제인 Keys and Rooms다.

문제의 조건은 다음과 같다.

• N개의 방이 주어지고 0번 방에서부터 시작한다. 이 방은 List<List<Integer>> 타입으로 주어진다.

• 각 방에는 다른 방으로 갈 수 있는 열쇠가 있다. 이 열쇠들은 List<Integer> 타입으로 주어진다.

• 0번 방에서부터 시작하여 열쇠들을 이용하여 모든 방에 방문할 수 있는지 여부를 확인하라.

• 방 이동에 제약은 없으며 0번 방을 제외한 모든 방은 방문한 적이 없는 상태다.

각 방과 방에 들어있는 열쇠는 리스트로 주어지는데 예를 들어 [[1], [2], [3], []]처럼 주어진다면 이는 총 4개의 방이 있으며 0번 방에는 1번 열쇠가, 1번 방에는 2번 열쇠가, 2번 방에는 3번 열쇠가 들어있는 상태다. 방 번호는 0에서부터 시작하여 N-1까지 기 때문에 위의 예시에서는 0번 방, 1번 방, 2번 방, 3번 방 순서대로 방문하여 모든 방을 방문할 수 있다.

 

만약 [[1,3], [3,0,1], [2], [0]]처럼 주어진다면 어떨까? 이는 총 4개의 방이 있으며 0번 방에는 1번, 3번 열쇠가, 1번 방에는 3번, 0번, 1번 열쇠가, 2번 방에는 2번 열쇠가, 3번 방에는 0번 열쇠가 들어있는 상태다. 이 경우 2번 방에 접근할 수 없기 때문에 모든 방을 방문할 수 없다.

 

이를 보고 떠오른 생각은 방과 열쇠를 그래프의 어떤 노드와 해당 노드에서 방문할 수 있는 이웃 노드라고 생각할 수 있겠다는 것이다. 그래서 이 이웃 노드를 타고 갈 수 있는 모든 노드를 방문할 때 그래프의 전체 노드를 방문할 수 있겠는지를 묻는 것이고 이는 BFS 탐색을 활용해볼 수 있겠다고 생각하여 다음과 같이 코드를 작성하였다.

import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        LinkedList<Integer> toVisitRooms = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        toVisitRooms.add(0);
        
        while(toVisitRooms.size() > 0){
            int nextRoom = toVisitRooms.pop();
            if(visited.contains(nextRoom)) continue;
            else visited.add(nextRoom);
            
            addRooms(toVisitRooms, rooms.get(nextRoom));
        }
        
        
        return visited.size() == rooms.size();
    }
    
    private void addRooms(LinkedList<Integer> visitRooms, List<Integer> rooms){
        for(Integer room: rooms){
            visitRooms.add(room);
        }
    }
}

 

이번에도 방문했던 방을 다시 방문하지 않도록 Set 자료구조를 활용했고 0번 방부터 시작하기 때문에 실제 로직을 수행하기 전에 0번 방을 Set에 등록했다. 그리고 하나씩 꺼내면서 해당 방에 들어있는 열쇠, 즉 다음에 갈 방을 LinkedList에 삽입했다. 이때 열쇠들은 List<Integer> 자료구조에 담겨있기 때문에 forEach 문을 사용하여 하나씩 꺼내서 삽입한 것이 특징이다.

 

방문한 방을 기록하는 용도도 되는 Set 자료구조의 크기를 전체 방의 크기와 비교하여 같다면 모든 방을 방문한 것이기 때문에 참을 반환하고 다르다면 그렇지 않은 것이기 때문에 거짓을 반환하도록 구현했다. 꽤나 간단하게 풀었기 때문에 이게 맞나 싶었는데 나쁘지 않은 결과(2ms)였다.

 

개선 방안을 찾아보기 위해 1ms 풀이를 찾아보니 다음과 같은 풀이를 하는 것을 볼 수 있었다.

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Stack<Integer> toVisit = new Stack<>();
        boolean[] unlocked = new boolean[rooms.size()];
        
        unlocked[0] = true;
        toVisit.push(0);
        int count = rooms.size() - 1;
        
        while (!toVisit.isEmpty()) {
            int room = toVisit.pop();
            
            List<Integer> keys = rooms.get(room);
            for (int key: keys) {
                if (!unlocked[key]) {
                    unlocked[key] = true;
                    count--;
                    toVisit.push(key);
                }
            }
        }
        
        return (count == 0);
    }
}

큐(LinkedList) 대신 스택을 활용하고 방문했던 방을 검사할 때는 boolean 배열을 쓰고 있었다. 단순히 인덱스만으로 방문 검사가 가능하다면 이렇게 boolean 배열을 활용하는 것도 괜찮은 것 같다. 로직 자체는 비슷한데 이번에는 방의 개수에서 1을 뺀 값으로 count 변수를 설정해두고 새로운 방에 방문할 때마다 1씩 빼고 있다. 0번째 방은 제일 처음에 방문하니 제외하고 나머지 방을 모두 방문했는지 확인하는 로직이다.

 

전체적인 풀이 방식 자체는 큰 차이가 없지만 최대한 원형(primitive) 자료형을 사용하여 구현했기 때문에 속도가 좀 더 빠른 것 같다. 꼭 필요하지 않다면 Set이나 List 같은 자료구조 대신 이렇게 원형 자료형의 배열이나 변수를 사용하는 것도 생각해봐야 할 것이다.

 

 

이걸 마지막으로 Queue, Stack 튜토리얼을 모두 끝낼 수 있었다. 프리미엄 계정이 아니기 때문에 풀 수 없는 문제도 있어 100%는 채우지 못했지만 2019년에 원형 큐를 잠깐 구현하고 말았던 것에 비하면 이번에는 끝까지 붙잡고 풀 수 있어 더욱 보람찼다. 얼른 다른 튜토리얼도 공부해야겠다.