DFS/BFS_LeetCode_keys-and-rooms

접근 방향

첫번째 방의 키를 stack에 추가해서,

stack에서 하나씩 빼면서 방을 돌아다니고,

들어간 방을 기록해서,

rooms와 숫자 비교를 한다.

 

실패 코드

시간 초과에 의해 실패

생각해보니 vistied를 Set으로 해야 할 것 같다. 중복된 방을 들어 갈 수 도있으니까.

혹은, 방을 들어가기 전에, visited에 있는지 검사하는 방법 또한 있음.

class Solution {
    func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
        var visited: [Int] = []
        var stack: [Int] = []
        var sol = false
        
        stack.append(contentsOf: checkKey(room: rooms[0]))
        visited.append(0)
        
        while stack.isEmpty != true {
            let nowEnter = stack.removeFirst()
            stack.append(contentsOf: checkKey(room: rooms[nowEnter]))
            visited.append(nowEnter)
        }
        
        if visited.count == rooms.count {
            sol = true
        }
        
        return sol
    }
    
    func checkKey(room : [Int]) -> [Int] {
        var keys: [Int] = []
        for key in room {
            keys.append(key)
        }
        
        return keys
    }
}

정답 코드

Runtime: 44 ms, faster than 25.64% of Swift online submissions for Keys and Rooms.

Memory Usage: 14.5 MB, less than 25.64% of Swift online submissions for Keys and Rooms.

class Solution {
    func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
        var visited: Set<Int> = []
        var stack: [Int] = []
        var sol = false
        
        stack.append(contentsOf: checkKey(room: rooms[0]))
        visited.insert(0)
        
        while stack.isEmpty != true {
            let nowEnter = stack.removeFirst()
            if visited.contains(nowEnter) == true {
                continue
            }
            
            stack.append(contentsOf: checkKey(room: rooms[nowEnter]))
            visited.insert(nowEnter)
        }
        
        if visited.count == rooms.count {
            sol = true
        }
        
        return sol
    }
    
    func checkKey(room : [Int]) -> [Int] {
        var keys: [Int] = []
        for key in room {
            keys.append(key)
        }
        
        return keys
    }
}

반성

상위 75%쯤의 속도가 나온다. 아무래도 removeFirst()의 문제가 아닐까?

그래서 진짜로 removeLast()로 바꿨더니 

Runtime: 40 ms, faster than 82.05% of Swift online submissions for Keys and Rooms.

Memory Usage: 14.3 MB, less than 79.49% of Swift online submissions for Keys and Rooms.

의 결과가 나왔다.

 let nowEnter = stack.removeLast()

당연히 stack이니까 LIFO로했어야지.........