[LeetCode] 841. Keys and Rooms (Swift, Python)

Keys and Rooms - LeetCode

 

풀이

 0번 방부터 탐색하는 dfs를 사용하면 된다. visited 배열을 만들어서 n번 방에 들어갈 수 있는지를 체크한다. 각 방에 들어갈 때마다 방에 있는 열쇠들을 for문을 통해서 아직 방문하지 않은 방의 열쇠일 경우 dfs 함수를 재귀적으로 호출해서 visited 여부를 바꿔준다.

 

코드

[Swift]

class Solution {
    var visited: [Bool] = [] // 각 방의 방문 체크 확인을 위한 배열
    var rooms: [[Int]] = [[]] // canVisitAllRooms 함수의 입력으로 주어진 rooms 배열을 담아주기 위한 배열
    
    func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
        visited = Array(repeating: false, count: rooms.count)
        self.rooms = rooms
        
        self.dfs(0) // 0번 방부터 dfs 탐색
        
        // 방문하지 못한 방이 있을 경우 false 리턴
        for visit in self.visited {
            if !visit {
                return false
            }
        }
        
        // 모두 방문했을 경우 true 리턴
        return true
    }
    
    func dfs(_ now: Int) {
        if self.visited[now] {
            return
        }
        
        // 현재 방 방문 체크
        self.visited[now] = true
        
        // 현재 방에 있는 열쇠들을 탐색하며 아직 방문하지 않은 방일 경우 dfs 재귀적으로 호출
        for room in self.rooms[now] {
            if self.visited[room] {
                continue
            }
            
            dfs(room)
        }
    }
}
 

[Python]

class Solution(object):
    visited = [] # 각 방의 방문 체크 확인을 위한 리스트
    rooms = [[]] # canVisitAllRooms 함수의 입력으로 주어진 rooms 배열을 담아주기 위한 리스트
 
    def canVisitAllRooms(self, rooms):
        self.visited = [False] * len(rooms)
        self.rooms = rooms
 
        self.dfs(0) # 0번 방부터 dfs 탐색
 
        # 방문하지 못한 방이 있을 경우 false 리턴
        if False in self.visited:
            return False
        
        # 모두 방문했을 경우 true 리턴
        return True
 
    def dfs(self, now):
        if self.visited[now]:
            return
        
        # 현재 방 방문 체크
        self.visited[now] = True
        
        # 현재 방에 있는 열쇠들을 탐색하며 아직 방문하지 않은 방일 경우 dfs 재귀적으로 호출
        for room in self.rooms[now]:
            if self.visited[room]:
                continue
 
            self.dfs(room)