Keys and Rooms

[Jinsujin]

문제

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

• 0~ n-1 로 표시된 n 개의 룸. 0번룸 뺴고는 모두 잠겨있다. ⇒ 0번방부터 탐색 시작
• 모든 룸을 방문해야 한다. 키 없이는 잠겨진 방에 방문할 수 없다.
• 각 방에 방문시, 열쇠 뭉치(distict keys) 를 찾을 수도 있다. 열쇠에는 번호가 적혀있고 해당 방을 열 수 있다. (열쇠뭉치는 모두 가져갈 수 있고 여러번 사용 가능. 중복된 열쇠를 방들에서 획득할 수 있음)
• 모든 룸을 방문할 수 있다면 true, 아니면 false 를 반환하라.

제약조건

• n == rooms.length
• 2 <= n <= 1000
  • 1000 은 10^3
  • O(n^2) 에 1000 을 넣으면 $10^6$
  • $10^6$ 은 $10^8$(1초 기준) 보다 작다 ⇒ O(n^2) 알고리즘으로 풀 수 있다!
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
  • 방 i 의 키 최대 개수 3000 개
• 0 <= rooms[i][j] < n
• All the values of rooms[i] are unique.

[Jinsujin]

DFS 풀이

각 방은 노드, 각 방에서 획득하는 열쇠 꾸러미는 간선들을 의미한다.
따라서 DFS, BFS 로 문제를 풀 수 있다.

DFS, BFS 시간 복잡도

• O(V+E) —노드개수 + 간선개수
• 문제의 노드개수(방) = 1000, 간선개수(열쇠꾸러미 개수) = 3000 이므로 O(1000+3000)

func solution1_2(_ rooms: [[Int]]) -> Bool {
   // 또는 set, dictionary 를 사용해서도 시간복잡도를 줄일 수 있다
    var check = Array(repeating: false, count: rooms.count)
    check[0] = true
    dfs(0)
    
    func dfs(_ roomNum: Int) {
        check[roomNum] = true
        
        for key in rooms[roomNum] {
            if check[key] { continue }
            dfs(key)
        }
    }
    return !(check.filter({$0==false}).count > 0)
}

[Jinsujin]

BFS 풀이

func solution(_ rooms: [[Int]]) -> Bool {
    
    var check = Array(repeating: false, count: rooms.count)
    var queue = [Int]()
    queue.append(0)
    check[0] = true
    
    while(!queue.isEmpty) {
        let current = queue.removeFirst()
        
        for next in rooms[current] {
            if check[next] { continue }
            queue.append(next)
            check[next] = true
        }
    }
    return !(check.filter({ $0 == false} ).count > 0)
}
solution([[1],[2],[3],[]]) //true
solution([[1,3],[3,0,1],[2],[0]])//false

[Jinsujin]

❌ 틀린 접근 방법

Union&Find

• 접근방법: Union 으로 방들을 연결한 후, 연결되지 않은 방이 있다면(find) false 반환하도록 했다
• Union&Find 는 a - b 가 양방향으로 연결되므로, 문제 요구조건인 단방향으로만 이동가능에 맞지 않다(열쇠를 획득하고 해당 방 이동)
• [[1],[],[0,3],[1]] 테스트 케이스에서 true 가 나와야 하지만 false 가 반환된다.

func solution1_3(_ rooms: [[Int]]) -> Bool {
    var graph = Array(repeating: 0, count: rooms.count)
    
    for i in 0..<rooms.count {
        graph[i] = i
    }
    
    // 1. rooms 를 loop 돌면서 union(연결) 한다
    for i in 0..<rooms.count {
        for key in rooms[i] {
            print(i, "->", key)
            union(a: i, b: key)
        }
    }
    
    //2.모든 노드가 연결되었는지 확인한다.
    for i in 0..<rooms.count-1 {
        let fa = find(i)
        let fb = find(i+1)
        if fa != fb { return false }
    }
    print(graph)
    return true
        
    func find(_ node: Int) -> Int {
        if node == graph[node] { return node }
        graph[node] = find(graph[node])
        return graph[node]
    }
    
    func union(a: Int, b: Int) {
        let fa = find(a)
        let fb = find(b)
        if fa != fb { graph[fa] = fb }
    }
}
// 정답: false
solution1_3([[1],[],[0,3],[1]]) // true