[Leetcode - Swift] 841. Keys and Rooms

문제

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

Keys and Rooms - LeetCode

 

풀이

그래프를 순회하는 문제. DFS와 BFS 둘 다 가능하다.

DFS의 런타임은 35ms로, 38ms인 BFS보다 더 빨랐다. 메모리도 0.1MB 덜 써서 공간복잡도에서도 효율적이었다.

 

BFS와 DFS의 템플릿을 그대로 이용하는 기본적인 문제였다. 기본의 중요성을 다시 한 번 느낀다!

 

👇🏻 BFS와 DFS 템플릿 보러가기

[PS] 간단한 Graph 개념과 BFS, DFS 템플릿

 

코드

import Foundation

class Solution {
    // dfs by 재귀
    func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
        var visited = [Int]()
        
        func dfs(_ current: Int) {
            visited.append(current)
            
            for room in rooms[current] {
                if !visited.contains(room) {
                    dfs(room)
                }
            }
        }
        
        dfs(0)
        return visited.count == rooms.count
    }
    
    //bfs by 큐
    func canVisitAllRooms2(_ rooms: [[Int]]) -> Bool {
        return bfs(rooms, 0).count == rooms.count
    }
    
    func bfs(_ rooms: [[Int]], _ start: Int) -> [Int] {
        var visited = [start], queue = [start]
        
        while !queue.isEmpty {
            let current = queue.removeFirst()
            
            for room in rooms[current] {
                if !visited.contains(room) {
                    queue.append(room)
                    visited.append(room)
                }
            }
        }
        return visited
    }
}