[Leetcode] 841. Keys and Rooms

⏱️ 소요시간

10분. 머리속에서 진짜로 방문을 열어보듯 코드도 똑같이 작성하면 된다!

📚 문제 요약

[leetcode] keys and rooms
n개의 방 모두 들어갈 수 있으면 true 아니면 false를 리턴.
단 1~n-1번방은 모두 잠겨있고, 0번방은 열려있다. 방에 들어가면 내가 들어갈 수 있는 방 번호의 키가 있다.

📑 풀이 요약

일단 이 문제는 DFS 문제로 해결할 수 있으므로 스택으로도, 재귀로도 해결할 수 있다. 풀이 방법은 동일하기에, 스택으로 푸는 방법 위주로 설명해보고자 한다!

stack에 들어갈 수 있는 방의 번호를 push하고 (처음 stack에는 0이 들어간다 - 0번방은 들어갈 수 있으니까)
방을 탐색해나가며, 내가 발견한 키를 stack에 push.

스택이 빌 때까지 스택에서 키를 꺼내며 방을 탐색한다. 이 때 한 번 탐색한 방은 다시 재탐색하지 않기 위하여 방문 여부를 체크하는 리스트 visited 생성

더 이상 탐색할 방이 없을 때 (스택이 빌 때) 내가 탐색한 방이 n개가 맞다면 true를, 그렇지 않다면 덜 탐색한거니 false를 리턴

💻 전체 코드 (1. 스택으로 작성)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        stack = [0] #0번방은 키 없이 들어갈 수 있음
        n = len(rooms) #들릴 방의 총 개수
        visited = [0 for _ in range(n)] #방문 여부를 기록하는 visited 리스트
        tot = 0 #내가 들린 방의 총 개수

        while stack: #들릴 방이 있을 때까지
            roomNum = stack.pop() # 방 번호를 pop하고
            if not visited[roomNum]: #방문 여부를 확인하여 방문하지 않은 경우
                visited[roomNum] = 1 #방문 처리를 한 다음에
                tot += 1 #sum(visited) 하기 싫어서 tot 변수 생성 : 방 들린 횟수 카운팅
                for key in rooms[roomNum]: #내가 들어간 방에서 키 모두 회수
                    stack.append(key) #회수한 키(= 들어갈 수 있는 방 번호)를 stack에 push
        if tot != n:#내가 탐방한 방이 n개가 아닌 경우 모두 들린게 아니니까
            return False #False를 리턴
        return True #n개인 경우 True를 리턴

💻 전체 코드 (2. 재귀함수로 작성)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [0 for _ in range(n)]
        global tot
        tot = 0
        def dfs(key):
            global tot
            if not visited[key]: #key번방을 가지 않았으면
                visited[key] = 1
                tot += 1
                for k in rooms[key]: #key번방에 가서
                    dfs(k) #갈 수 있는 방 계속 탐방
        dfs(0)
        if tot == n:
            return True
        return False