[LeetCode] 841. Keys and Rooms

문제

0번부터 n - 1번까지 n개의 방이 있고, 0번 방을 뺀 나머지는 모두 잠겨 있다.
각 방에는 다른 방을 여는 열쇠가 들어 있으며, rooms[i]는 i번 방에 있는 열쇠 목록이다.

0번 방에서 출발해 모든 방에 들어갈 수 있으면 true, 아니면 false를 반환한다.

입력: rooms = [[1],[2],[3],[]]
출력: true
// 0 → 1 → 2 → 3 순서로 모든 방에 들어갈 수 있다

입력: rooms = [[1,3],[3,0,1],[2],[0]]
출력: false
// 2번 방 열쇠는 2번 방 안에만 있다

접근

방을 노드, 열쇠를 간선으로 보면 그래프 문제가 된다.

0번 노드에서 출발해 모든 노드에 도달할 수 있는가?

결국 0번에서 시작하는 그래프 탐색(BFS/DFS)을 한 번 돌리고, 방문한 방의 수가 전체 방의 수와 같은지 비교하면 된다.

1. 방문한 방을 Set에 기록한다.
2. 큐에 0번 방을 넣고 시작한다.
3. 큐에서 방을 하나 꺼내 방문 처리하고, 그 방에 있는 열쇠 중 아직 가지 않은 방을 큐에 넣는다.
4. 큐가 비면 방문한 방 수 === 전체 방 수를 반환한다.

풀이

function canVisitAllRooms(rooms: number[][]): boolean {
    const visited = new Set<number>();

    let keys = [0];
    while (keys.length) {
        const room = keys.shift();
        visited.add(room);
        for (const key of rooms[room]) {
            if (!visited.has(key)) keys.push(key);
        }
    }

    return rooms.length === visited.size;
};

개선할 점

제출은 통과하지만 다듬을 곳이 두 군데 있다.

1. 방문 처리를 큐에 넣을 때 한다

지금 코드는 방을 꺼낼 때 방문 처리를 한다. 그래서 아직 꺼내지 않은 방이 큐에 여러 번 들어갈 수 있고, 그 방의 열쇠 목록도 여러 번 다시 훑게 된다.
넣을 때 방문 처리를 하면 각 방은 큐에 정확히 한 번만 들어간다.

2. shift() 대신 스택(pop())을 쓴다

Array.prototype.shift()는 뒤의 요소를 한 칸씩 당기므로 O(n)이다.
이 문제는 방문 순서는 상관없고 도달 가능 여부만 묻기 때문에, pop()(O(1))을 쓰는 DFS로 바꿔도 답은 같다.

덤으로 strict 모드에서는 shift()의 반환 타입이 number | undefined라 rooms[room]에서 타입 에러가 난다. while문 안에서 꺼낸 값을 !로 단언하면 해결된다.

function canVisitAllRooms(rooms: number[][]): boolean {
    const visited = new Set<number>([0]);
    const stack = [0];

    while (stack.length) {
        const room = stack.pop()!;
        for (const key of rooms[room]) {
            if (visited.has(key)) continue;
            visited.add(key);
            stack.push(key);
        }
    }

    return visited.size === rooms.length;
}

복잡도

• 방의 수를 N, 전체 열쇠 수를 K라고 하면
• 시간 복잡도: O(N + K). 각 방은 한 번씩 꺼내고, 각 열쇠는 한 번씩 확인한다.
• 공간 복잡도: O(N). visited와 스택에 방 번호가 최대 N개 들어간다.

정리

• "열쇠로 다른 방을 연다"는 "노드에서 간선을 따라간다"와 같다. 도달 가능성 문제는 그래프 탐색으로 푼다.
• 방문 처리는 큐(스택)에 넣는 시점에 해야 중복 탐색이 생기지 않는다.
• 순서가 상관없는 탐색이라면 shift()보다 pop()이 싸다.